이진탐색/이분탐색 (Binary Search) 알고리즘

이진탐색의 과정

 

여기보면 알기쉽게 설명돼 있다.

 

 

1. STL사용버전

binary_search() 사용

#include <bits/stdc++.h>
using namespace std;
 
int main(void)
{
    int arr[10]= { 0, 1, 3, 3, 3, 4, 6, 9, 10, 11 };
    sort(arr, arr + 10);
    int size = 10;
    int to_find = 9;
    cout << binary_search(arr, arr + size, to_find) << endl;
    return 0;
}

binary_search()대신 lower_bound()를 사용하면 더 유연하다.

binary_search()는 존재여부만 리턴해서 있으면 1 없으면 0을 리턴하는데, 

lower_bound는 iterator를 리턴해서 위치나 값까지 알 수 있다.

#include <bits/stdc++.h>
using namespace std;
 
int main(void)
{
    int arr[10] = { 0, 1, 3, 3, 3, 4, 6, 9, 10, 11 };
    sort(arr, arr + 10);
    int size = 10;
    int to_find = 9;
    cout << (*lower_bound(arr, arr + size, to_find) == to_find ? 1 : 0) << endl;
    return 0;
}
 

 

 

2. 직접구현 - 나이브하게 시도해본 버전

아무 생각없이 의식의 흐름대로 구현하면 아래처럼 되는데

bool my_bsearch(int in[], int N, int find) {
       int left = 0, right = N - 1;
       while (left <= right) {
              int mid = (left + right) / 2;
              if (in[mid] == find) return true;
              if (in[mid] < find) left = mid;
              else right = mid;
       }
       return false;
}
 

left=3, right=4와 같은 상황이 됐을때 mid = 3이되고 무한루프에 빠진다 ㅠ

integer 나눗셈의 특수성에 기인한 현상으로 잡기가 생각보다 까다롭다.

 

 

이 상황을 피해보겠다고 조건문을 추가하면 아래처럼 덕지덕지가 되는 상황 ㅠ

bool my_bsearch(int in[], int N, int find) {
    int left = 0, right = N - 1;
    do {
        int mid = (left + right) / 2;
        if (in[left] == find) return true;  // A
        if (in[mid] == find) return true;
        if (in[right] == find) return true; // A
        if (in[mid] < find) {
            if (left == mid) break;  // B
            left = mid;
        }
        else {
            if (right == mid) break; // B
            right = mid;
        }
 
        if (in[mid] < find) left = mid;
        else right = mid;
    } while (left < right);  // C
    return false;
}

(경계선 처리가 힘들고 주석 A, B, C 부분이 맘에 안든다)

일단 위처럼 덕지덕지가 되는 코드는 랜덤TC에 맞춰서 수정했을뿐 재활용 가치도 없고, reproduce도 불가능하다. 한마디로 쓰레기

 

3. 해당 문제점들을 개선한 버전

덕지덕지 조건문 붙이는게 싫으면 다음처럼 log연산이라 1000번이면 충분하고도 남는다는 점을 활용해서 T를 추가하고,

1000번이상이면 break시킨다음 left랑 right인덱스도 살펴보는 방법이 있다

(A, B부분)

bool my_bsearch(int in[], int N, int find) {
       int left = 0, right = N - 1;
       int T = 1000;  // A
       while (left <= right && T--) {  // A
              int mid = (left + right) / 2;
              if (in[mid] == find) return true;
              if (in[mid] < find) left = mid;
              else right = mid;
       }
       if (in[left] == find || in[right] == find) return true;  // B
       return false;
}

이정도만 해도 실전에서는 구현해볼만한 난이도가 된다.

 

그러나 면접용으로 코딩을 준비중이라면, 위의 T로 루프탈출을 하는것보다 아래버전을 외워두는게 좋다.

bool my_bsearch(int in[], int N, int find) {
    int left = 0, right = N - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (in[mid] == find) return true;
        if (in[mid] < find) left = mid+1;
        else right = mid-1;
    }
    return false;
}

초기 버전에서 mid+1, mid-1 부분만 +1, -1 가미해준 식으로 바뀐거라 뭐그리 외우기 어렵지도 전혀않다.

위 함수에서 return 부분만 살짝 바꿔주면 lower_bound랑 비슷한 기능을 하도록 수정할 수 있다.

(c++에서는 그냥 lower_bound쓰면 되지만, java에서는 지원하지 않으니 필요할수도..)

int my_lower_bound(int in[], int N, int find) {
    int left = 0, right = N - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (in[mid] == find) return mid;
        if (in[mid] < find) left = mid+1;
        else right = mid-1;
    }
    return left;
}

 

결론

꼭 필요한 경우가 아니면 STL쓰는게 좋고, 직접구현은 에러발생하기가 너무나 쉽다.

T로 루프탈출하는 버전을 쓰거나, 젤 아래버전을 외워두자.