Binary Search Algorithm (이진 검색 알고리즘)

Binary Search는 순서대로 정렬된(sorted) 리스트에서 아이템을 찾는데 유용한 알고리즘이다.

Binary Search는 아이템이 있는 범위까지 계속해서 반으로 나누면서 찾는다.

1부터 10까지 수 중 아무거나 하나를 생각해서 맞추는 게임의 알고리즘과 동일하다.

Binary Search의 의사 코드는 다음과 같다.

< 1부터 n까지 숫자중 하나 맞추기 게임 >

1. min은 범위 중 가장 낮은 것, max는 범위 중 가장 높은 것이다.

min = 1, max = n

2. min과 max의 평균값을 구해서 반내림을 한다. 이게 추정치다. (정수가 되도록)

3. 만약 숫자를 맞췄다면, stop!

4. 만약 추정치가 너무 낮다면 min을 그 추정치보다 높게 변경.

5. 만약 추정치가 너무 높다면 max를 그 추정치보다 낮게 변경.

6. 만약 max - min 이 -1 이라면? 해당 숫자를 못 찾은 것이므로 에러 리턴

7. 2번으로 돌아간다.

유니티 개발능력을 키우기  위해

알고리즘을 배우면서는 C#을 사용해보기로 했다.

C#을 쓰는게 이번이 처음이라 몇가지 코멘트를 달겠다.

class BinarySearch {
    public static void Main() {
        int hide, seek;
        int count = 0;
        bool found = false;
        
        // 입력받은 길이 만큼의 array를 만든다.
        Console.WriteLine("Input Array Size : ");
        int size = int.Parse(Console.ReadLine());
        int[] numbers = new int[size];
        for (int i = 0; i < size; i++) {
            numbers[i] = (i + 1) * 10;
        }
        
        // binary search를 할 범위이다.
        int min = 0;
        int max = numbers.Length - 1;
        // array 중 랜덤한 숫자를 뽑아 찾을 수로 정한다.
        Random random = new Random();
        hide = numbers[random.Next(numbers[min], numbers[max])];
        
        // min과 max로 range를 좁히면서 binary search를 한다.
        do {
            count++;
            int guess = (min + max) / 2;
            seek = numbers[guess];
            if (seek > hide) {
                max = guess - 1;
            } else if (seek < hide) {
                min = (guess) + 1;
            } else if (max - min < 0) {
                Console.WriteLine("Failed to find Hide.");
                break;
            } else {
                Console.WriteLine("Gotcha! Hide is {0}, Search Count is {1}", hide, count);
                found = true;
            }
        } while (!found);
    }
}
 

C# 문법

- Console.WriteLine() 은 자바에서 System.out.println()과 같다. 콘솔에 해당 문자열을 출력한다.

{index} 로 변수를 인자로 넘겨 보여줄 수도 있다.

- array의 길이를 구하기 위해 array.Length; 를 사용한다.

- 사용자로 부터 받는 input를 정수형으로 변환하기 위해 int.Parse(Console.readLine());를 사용했다.

Binary Search의 이점

Binary Search를 해보니 7000개의 원소가 있는 array에서

숫자 하나를 13번의 search 만에 찾아버렸다.

Linear Search보다 상당히 효율성이 있는 것을 알게됬다.

Linear Search와 Binary Search의 성능 차이는 array의 원소가 많아질 수록 더욱 잘 느낄 수 있다.

Binary Search는 정답이 있는 범위를 매 추정마다 반으로 줄여나가기 때문이다.

따라서 8개의 원소가 있는 array에서 Binary Search로 숫자를 찾을 경우

최소 1번, 최대 4번만에 찾을 수 있다.

16개의 원소가 있는 array는 최소 1번, 최대 5번 만이다.

아래 사진처럼, 약 200개의 원소가 있는 array라도 21번의 search만에 원하는 값을 찾을 수 있다.