이진탐색(Binary Search)

 

 

선형(순차) 탐색(Linear Search) 은 부르트포스(brute force)의 일종으로 무식하게 처음부터 끝가지 모든 자료를 비교해가면서 원하는 값을 찾는 무식한 방법이라고 하였다. 그래서 찾는것이 앞부분에 있으면 다행히 빨리 찾을수 있지만 뒤에 있다면 worst case 로 탐색하는데 O(N)이 걸린다.

이진탐색(Binary Search) 알고리즘은 선형탐색이 가지고 있는 단점을 보완할 수 있는 알고리즘인데 아무리 자료가 많아도 탐색하는데 O(log N) 이 걸린다. 선형탐색에 비해 성능면에서 엄청 좋은것이다. 

그래서 실무에서는 선형탐색보다 이진탐색을 더 많이 사용한다.

대신 조건이 있는데 선형탐색은 자료가 정렬될 필요가 없지만 이진탐색은 내부 알고리즘 로직에 의해 반드시 자료가 정렬되어 있어야만 한다. 

그리고 이진검색은 분할 정복(Divide and Conquer)의 로 이루어 지는데 이유는 검색 범위를 자료의 1/2씩 줄여 나가면서 원하는 데이터를 검색하는 알고리즘이기 때문이다

정렬에 대한 것은 아래 글들을 참고 하면 된다.

 

1. 선택정렬(Selection Sort)
2. 삽입정렬(Insertion Sort)
3. 버블(거품)정렬(Bubble Sort)
4. 머지소트(Merge Sort)
5. 퀵정렬(Quick Sort)
6. 힙정렬(Heap Sort)
7. 쉘정렬(Shell Sort)
8. 기수정렬((Radix Sort) 

 

성능이 왜 좋고 알로고리즘 수행전 자료가 왜 정렬되어 있어야 하는지 알고리즘의 내부 로직을 살펴보면 쉽게 이해가 간다.

이미지를 보면서 동작원리를 살펴보자

 

위와 같이 list = { 10, 14, 19, 27, 31, 33, 35, 42, 44 } 가 있고 이진검색을 통해 31을 찾는다고 하자. 

이진검색을 수행하기전에 내부적으로 자료는 정렬되어 있어야 한다고 했었는데 위의 리스트는 오름차순으로 정렬된 상태이다.

첫번째로, 우리는 아래 공식에 의해 배열의 절반(half)를 결정해야 한다.

 

mid  = low + (high - low)/2

 

처음 low 값은 배열의 0번째가 되고 high는 배열의 맨끝인 9가 된다.  그럼 위 공식에 의해 mid 는 

 

mid = 0 + (9 - 0)/2 = 4가 된다 (4.5의 integer 값이다.) 

 

mid=4 인 인덱스는 값이 27인데 우리는 31을 찾고 싶어한다.  27 < 31이 더 크므로 27 을 포함한 좌측에 있는것들은 모두 31보다 작을것이기 때문에 더이상 검색할 필요가 없다. 버리는 것이다. (why 정렬이 필요한지 여기서 이해가 갈 것이다.)

이제 우리는 자료의 1/2을 버리고 27보다 큰 {31, 33, 35, 42, 44} 에서 검색을 할 필요가 있다.

 

low 가 바뀌었으니 low 값을 = mid(4) + 1 로 갱신할 필요가 있다. 

 

low = mid + 1 

mid = low + (high - low) / 2

 

이제 mid = 5 + ( 9 - 4)/2 = 7이 된다.

 

인덱스 7에대한 값은 35이고 우리가 찾고자하는 31보다 크다. 따라서 35포함하여 우측에 있는것들은 검색할 필요가 없다. 

또 자료의 1/2을 버리고 {31, 33} 에 대해서만 검색을 하면 된다.

다시 mid 값을 계산해야 하는데 

low 는 이전과 그대로이고 high 만 변경해주면 된다.

 

high = mid-1 = 6

mid = low + (high - low) / 2 = 5 + (6 - 5)/2  = 5

 

 

이제 mid = 5번 값이 31과 같다. 이 처럼 자료가 정렬되어 있으면 찾으려는 값기준으로 좌측을 검할지 우측을 검색할지 결정이 되기 때문에 검색할 자료의 구조는 1/2씩 계속 감소하게 되어 있다. 

 

이진검색을 구현하기위해서 2가지 방법이 있는데 하나는 재귀(recursion)적인 방법과 비재귀적인 방법 둘다 가능한다.

재귀적인 방법은 함수내에 함수를 또 호출하기 때문에 성능상 비재귀적인 방법보다 나쁘다. 

또 콜스택(CALL STACK) 이슈도 발생할 수 있다. 

따라서 여기에선 비재귀적인 방법으로 구현한다.

 

    public static  int binarySearch(int[] list, int key) {
        // 맨처음 low = 0, high는 배열의 끝이다.
        int low = 0;
        int high = list.length - 1;
 
        while (low <= high) {
            int mid = low + (high - low)/2; // mid 값을 계산.
 
            if (key > list[mid]) // 키값이 더 크면 왼쪽을 버린다.
                low = mid + 1;
            else if (key < list[mid]) // 키값이 더 작으면 오른쪽을 버린다.
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found
    }

 

 

이진탐색은 코딩테스트 문제에서 자주 나오는 것 중 하나이기 때문에  개념을 잘 알아 두어야 한다. 

 

연습문제

• 백준 1920 - 수 찾기 
• 백준  2512 - 예산 : https://www.acmicpc.net/problem/2512 
• 백준 1654 - 랜선자르기 : https://www.acmicpc.net/problem/165