이분탐색 (Binary Search) 기법

오름차순으로 정렬된 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘입니다. 기초적인 알고리즘인 만큼 PS에서 자주 사용할일은 없지만 문제의 조건에서 주어진 수의 규모가 크고 반복해야 할 일이 많다면 해당 기법을 시도해보아야 합니다.

 

대표적 문제 : 프로그래머스 - 입국심사

https://programmers.co.kr/learn/courses/30/lessons/43238

코딩테스트 연습 - 입국심사

이분탐색 과정을 거치지 않으면 이러한 큰 수를 N제곱의 시간복잡도로 해결하게 된다.

 

기본적인 이분탐색 코드는 다음과 같다.

int binarySearch(int arr[], int n, int key) {
	int start = 0;
	int end = n;
	int mid;
	while (end-start >=0) { 
		mid = (start + end) / 2;
		if (arr[mid] == key)
			return mid;
		else if (arr[mid] < key) {
			end = mid - 1;
		}
		else {
			start = mid + 1;
		}
	}
}

계속해서 중간값을 변경해나가며 key를 찾아내는 방식.

while문으로 반복해서 mid값을 변경해 반복범위를 반으로 좁혀나갑니다.

 

이분탐색을 이용해 문제를 해결할때는 Start와 End값을 잘 적용하는게 중요합니다.

위의 '입국심사'문제의 경우 가장 초기의 시간 (1분)을 Start 로 설정하고 가장 최악의 시간 (가장 오래걸리는 심사관 * N) 을 End 값으로 설정하여 이분탐색을 실행해 최소의 값을 구합니다.

 

일반적인 순회탐색보다 이분탐색은 ( logN ) 의 시간복잡도를 가지며 훨씬 빠른 성능을 보입니다.