[Algorithm] 이진 탐색 (이분 탐색, Binary Search) 코드와 시간 복잡도

인트로

이진 탐색이란 정렬된 배열에서 특정 값을 찾는 탐색 알고리즘이다.

이진 탐색은 배열의 중간을 기준으로 데이터를 탐색하기 때문에 반드시 데이터가 정렬된 상태로 존재해야 한다.  

 

이진 탐색의 시간 복잡도는 O(logN)으로 배열을 전수 조사하는 O(N)에 비하면 상대적으로 빠른 탐색 알고리즘에 속한다. O(logN)만에 값을 찾을 수 있는 이유는 중간을 기준으로 탐색 대상을 절반씩 줄여나가기 때문이다.

 

본 포스팅 말미에 코드와 시간 복잡도 계산법을 상세히 적어놨으니 참고하시길 바랍니다.

이진 탐색 : 개념

이진 탐색은 내가 찾고자 하는 값이 정렬된 배열의 중간 값보다 크면 중간값을 포함한 하위 값들은 탐색 대상에서 제외된다. 반대로 찾고자 하는 값이 배열의 중간 값보다 작으면 중간 값을 포함한 상위 값들은 탐색에서 제외된다.

 

정리하면 중간값과 찾으려는 값의 대소를 비교한 뒤 탐색 범위를 반으로 줄여가며 값을 찾는 탐색 알고리즘이다.

https://blog.penjee.com/binary-vs-linear-search-animated-gifs/

 

이진 탐색 : 코드

lt와 rt 그리고 mid 변수의 값을 변경하며 탐색의 범위를 줄여가는 것이 이진 탐색의 전부이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	int n, data, target, res = -1, lt = 0, rt, mid;
	vector<int> vec;

	cin >> n >> target;

	for (int i = 0; i < n; i++)
	{
		cin >> data;
		vec.push_back(data);
	}

	rt = n - 1;
	sort(vec.begin(), vec.end());

	while (lt <= rt)
	{
		mid = (lt + rt) / 2;

		if (vec[mid] == target)
		{
			res = mid;
			break;
		}
		else if (vec[mid] > target) rt = mid - 1;
		else if (vec[mid] < target) lt = mid + 1;
	}

	cout << "target index : " << res;
}

이진 탐색 : 시간 복잡도

운이 좋으면 찾고자 하는 값이 중간값과 동일해서 탐색이 끝나지만 최악의 경우 남은 데이터가 하나가 될 때까지 탐색을 반복한다. 이를 고려해 시간 복잡도를 계산해보자.

 

전체 데이터의 수를 $N$이라고 하자. 

1) 첫 번째 탐색 후 절반만 남아 남은 수가 $\frac{N}{2}$개.

2) 두 번째 탐색에서 다시 절반만 남아 남은 수가 $\frac{N}{2} \times \frac{1}{2}$개.

3) 세 번째 탐색에서 다시 절반이 남아 남은 수가 $\frac{N}{2} \times \frac{1}{2}\ \times \frac{1}{2}$개.

 

k) 규칙을 찾아보면 k번째 탐색에서 남은 데이터 수는$\left ( \frac{1}{2} \right )^{k}\times N$이 된다. 

 

최악의 경우에선$\left ( \frac{1}{2} \right )^{k}\times N = 1$이 될 때까지 탐색을 하게 됨을 다시 한 번 기억하자.

위 식의 양변에 $2^{k}$를 곱하면 $2^{k} = N$가 되고 다시 양변에 $log_2$를 취하면 최종 식은 $k = log_2N$이 된다.

 

여기서 k는 탐색 횟수로 N에 따라 시행 횟수는 $log_2N$이 된다. 따라서 시간 복잡도는 $O(log_2N)$으로 나타낼 수 있다.