이분탐색

이분탐색이란?

정렬된 배열에서 특정 데이터를 빠르게 찾는 탐색 알고리즘이다. 데이터를 찾을 때 순차가 아닌 범위를 반씩 좁혀나가며 탐색한다. 쉽게 표현하면 업다운 게임에서 1~50숫자중 하나를 맞출 때 25를 처음에 외치는 이유와 비슷하다.

그림과 같이 배열이 존재할 때 22번을 찾는 방법은 다음과 같다.

해당 그림으로 배열에서 22를 찾는 방법이 정리되어 있다. 이를 통해 이분 탐색 알고리즘을 정리하면 다음과 같다.

1. 배열의 시작(st)과 끝(en) 인덱스를 찾는다.
2. 배열의 중심을 찾는다. (mid = (st+en)/2)
3. 배열의 중심값과 비교하여 탐색 범위를 조절한다
   3-1. 중심값보다 찾는 값이 클 경우 : st = mid +1
   3-2. 중심값보다 찾는 값이 작을 경우 : en = mid - 1;
4. 원하는 값을 찾았거나 시작점이 끝점보다 커지면 탐색을 종료한다.

이분 탐색 알고리즘의 정리는 위 내용으로 끝난다. 그러면 이제 코드를 작성하면 다음과 같다.

2. 코드

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

int a[100002];
int n, num;

bool binarySearch(int num)
{
	int st = 0;
	int en = n-1;
	
	while(st <= en)
	{
		int mid = (st+en)/2;
		
		if(a[mid] == num)
		{
			return 1;
		}
		else if(a[mid] < num) st = mid + 1;
		else en = mid - 1;
	}
	
	return 0;
}

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);
	
	cin >> num;
	cout << binarySearch(num);
	
	return 0;
}

// 입력
5
4 1 5 2 3
5

// 출력
1

마무리

이분 탐색은 생각보다 간단하나 이를 변형하고 문제로 풀면 많이 어렵다고 들었다.
또한 Parametric Search에도 연관이 있다 들었는데 이런 경우는 조금만 틀어도 난이도가 극악으로 치솟는다는데 상당히 많은 문제를 풀어봐야 할 듯하다.

Reference
[실전 알고리즘] 0x13강 이분탐색 - BaaaaaaaarkingDog