Part2. C# 기초 다지기(7. 선형탐색과 이진탐색)

선형탐색과 이진탐색

 

이번 포스팅에서는 배열 내에 원하는 값을 찾고자 할 때, 대표적으로 사용할 수 있는 선형탐색과 이진탐색에 대해서 정리했습니다.

---

선형탐색

 

선형탐색은 배열의 모든 요소를 하나하나 키값(찾고자 하는 값)과 비교하여 같으면 그 값의 인덱스를 결과로 출력합니다.

데이터의 개수가 N일 때 시간복잡도가 O(N)인 알고리즘입니다. 데이터의 길이가 길면 비효율적이지만 그만큼 단순하고 구현하기 쉽습니다. 다음은 1~1000까지의 정수 20개를 랜덤으로 생성하고 정렬 전후 선형탐색을 사용하여 비교 횟수를 출력하는 예제입니다.

---

using System;
using System.Data;

namespace LinearSearch_exam
{
    internal class Program
    {
  
        static void Main(string[] args)
        {
            Random rnd = new Random();
            int[] v = new int[20];

            Console.WriteLine("정렬 전");
            for(int i = 0; i < v.Length; i++)
            {
                v[i] = rnd.Next(1000);
                Console.Write("{0, 5}{1}", v[i], (i % 10 == 9) ? "\n" : "");
            }
            Console.Write("=> 검색할 숫자를 입력하세요: ");
            int key = int.Parse(Console.ReadLine());
            LinearSearch(v, key);
            Console.WriteLine();

            Array.Sort(v);
            Console.WriteLine("정렬 후");
            for (int i = 0; i < v.Length; i++)
            {
                Console.Write("{0, 5}{1}", v[i], (i % 10 == 9) ? "\n" : "");
            }
            Console.Write("=> 검색할 숫자를 입력하세요: ");
            key = int.Parse(Console.ReadLine());
            LinearSearch(v, key);

        }

        private static void LinearSearch(int[] arr, int key)
        {
            int count = 0;
            for (int i = 0; i < arr.Length - 1; i++)
            {
                count++;
                if (arr[i] == key)
                {
                    Console.WriteLine("arr[{0}] = {1}", i, key);
                    Console.WriteLine("선형탐색의 비교횟수는 {0}회입니다.", count);
                    break;
                }
            }
        }
    }
}

결과

정렬 전
  509  555  224   51   51  169  346   69  340  211
  392  235  364  736  729  356  146  968  819  548
=> 검색할 숫자를 입력하세요: 146
arr[16] = 146
선형탐색의 비교횟수는 17회입니다.

정렬 후
   51   51   69  146  169  211  224  235  340  346
  356  364  392  509  548  555  729  736  819  968
=> 검색할 숫자를 입력하세요: 729
arr[16] = 729
선형탐색의 비교횟수는 17회입니다.

---

 

선형탐색의 경우 정렬 여부와 상관없이 동일 위치에 있는 값은 동일한 비교횟수를 가지는 것을 알 수 있습니다.

 

이진탐색

 

이진탐색은 배열의 요소들이 정렬되어 있을 때만 적용할 수 있습니다. 배열의 중간값과 키값을 비교하여 중간 값보다 키값이 크면 중간 아래쪽 자료는 검색하지 않습니다. 한번 비교할 때마다 검색할 자료가 1/2씩 줄어들기 때문에 시간 복잡도는 O(lnN)입니다.

 

다음 예제는 위 선형탐색과 동일하게  1~1000 까지의 정수 20개를 랜덤으로 생성하고 정렬 후 이진탐색을 이용하여 비교 횟수를 출력합니다.

---

using System;
using System.Data;

namespace BinarySearch_exam
{
    internal class Program
    {
  
        static void Main(string[] args)
        {
            Random rnd = new Random();
            int[] v = new int[20];

            Console.WriteLine("정렬 전");
            for(int i = 0; i < v.Length; i++)
            {
                v[i] = rnd.Next(1000);
                Console.Write("{0, 5}{1}", v[i], (i % 10 == 9) ? "\n" : "");
            }
 
            Array.Sort(v);
            Console.WriteLine("정렬 후");
            for (int i = 0; i < v.Length; i++)
            {
                Console.Write("{0, 5}{1}", v[i], (i % 10 == 9) ? "\n" : "");
            }
            Console.Write("=> 검색할 숫자를 입력하세요: ");
            int key = int.Parse(Console.ReadLine());
            BinarySearch(v, key);

        }

        private static void BinarySearch(int[] arr, int key)
        {
            int count = 0;
            int low = 0;
            int high = arr.Length - 1;
            while(low <= high)
            {
                count++;
                int mid = (low + high) / 2;
                if (arr[mid] == key)
                {
                    Console.WriteLine("arr[{0}] = {1}", mid, key);
                    Console.WriteLine("이진탐색의 비교횟수는 {0}회입니다.", count);
                    break;
                }
                else if (arr[mid] < key)
                    low = mid + 1;
                else
                    high = mid - 1;
            }

        }

    }
}

결과

---

정렬 전
  349  424  161  608  597  429  544   74  620  291
  660  349  403  614  228  533  416  818  614  923
정렬 후
   74  161  228  291  349  349  403  416  424  429
  533  544  597  608  614  614  620  660  818  923
=> 검색할 숫자를 입력하세요: 620
arr[16] = 620
이진탐색의 비교횟수는 5회입니다.

---

17번째 위치에 있는 숫자의 비교 횟수가 5회로 선형탐색에 비해 매우 빠르다는 것을 알 수 있습니다.

---

[Review]
"초보자를 위한 C# 200제(2판)" / 저자  강병익