[알고리즘] 이분 탐색(Binary Search)

시간복잡도: O(logN)

 

선형탐색은 O(N)에 동작하지만, 이분탐색은 O(logN)에 동작하므로, N이 커지면 커질수록 둘은 아주 큰 속도 차이가 발생한다.

 

이분탐색은 정렬되어 있는 배열에서 특정 데이터를 찾기 위해서 모든 데이터를 순차적으로 확인하는 대신 탐색 범위를 절반으로 줄여가면서 찾는 탐색 방법이다.

 

STL sort 함수를 사용해서 정렬시킨 후에 st와 en을 각각 배열의 처음과 끝으로 두고, mid = (st+en)/2를 하여 mid를 설정한다. 

이후 찾고 싶은 데이터를 찾아 보고 없으면 st = mid + 1 or en = mid - 1로 변경해서 범위를 절반으로 줄이도록 한다. 다시 mid = (st+en)/2를 하고,  target을 찾아나가는 것을 반복한다. 

 

 

 백준 1920번: 수찾기(C++)

 

// baekjoon online judge 1920번

#include <bits/stdc++.h>
using namespace std;

int n;
int a[1005];

int binarysearch(int tg){
	int st = 0;
    int en = n-1;
    while (st <= en) {
    	int mid = (st + en) / 2;
        if(a[mid] < tg){
        	st = mid + 1; 
        }
        else if (a[mid] > tg){
        	en = mid - 1;
        }
        else return 1;
    }
    return 0; // st > en일 경우 while 문을 탈출 한다.
}

int main(){
	ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    sort(a, a+n);
    int m;
    cin >> m;
    while(m--){
    	int t;
        cin >> t;
        cout << binarysearch(t) << '\n';
    }
}

 

하지만 C++에는 이미 STL로 구현이 되어 있기 때문에 binarysearch STL을 사용하면 매우 편리하게 바로 이분탐색을 사용할 수 있다.

 

// baekjoon online judge 1920번 STL 사용

#include <bits/stdc++.h>
using namespace std;

int n;
int a[1005];

int main(){
	ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    sort(a, a+n);
    int m;
    cin >> m;
    while(m--){
    	int t;
        cin >> t;
        cout << binarysearch(a, a+n, t) << '\n';
    }
}