1. 알고리즘 이해

이진 탐색은 자료구조에서 원하는 값을 찾는 탐색 알고리즘 중의 하나이다. 앞에서부터 하나씩 순차적으로 탐색하는 순차 탐색 (선형 탐색)과 달리, 이진 탐색은 찾으려는 key 값과 배열의 중간값을 비교하여, 그에 따라 탐색 범위를 절반씩 줄여나간다는 게 핵심이다!
key가 중간값보다 작은 경우 뒷부분은 볼 필요가 없고, key가 중간값보다 큰 경우 앞부분은 볼 필요가 없다. 단, 주의할 점은 이진 탐색은 정렬된 배열에서만 사용할 수 있다는 것이다.

2. 코드로 구현

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

// 순차 탐색
int LinearSearch(int n, int* arr, int key){
	for(int i = 0; i < n; i++){
		if(arr[i] == key)
			return i;
	}
	return -1; // not found
}

// 이진 탐색 
int BinarySearch(int n, int* arr, int key){
	int low = 0, high = n - 1, mid;

	while(low <= high){
		mid = (low + high) / 2;

		if(key == arr[mid]) return mid;
		else if(key < arr[mid]) high = mid - 1;
		else low = mid + 1; 
	}

	return -1; // not found
}

int main(){
	int arr[10] = {0, 4, 9, 2, 1, 8, 6, 7, 5, 3};

	// 순차 탐색
	int a = LinearSearch(10, arr, 9);
	cout << a << "\n"; // 2

	// 이진 탐색은 정렬된 배열에서만 사용할 수 있다.
	sort(arr, arr + 10); 

	// 이진 탐색
	int b = BinarySearch(10, arr, 7);
	cout << b << "\n"; // 7

	return 0;
}

3. 시간복잡도

(1) 직관적인 이해

이진 탐색은 입력 데이터의 크기가 2배로 늘어나도 연산 횟수는 1번밖에 늘어나지 않는다. 즉, 이진 탐색은 입력 크기에 따라 로그 스케일로 연산 횟수가 증가한다.

선형 탐색은 input size에 비례해서 검색 시간이 늘어나므로 O(N)이지만, 이진 탐색은 검색 범위가 절반씩 줄어들기 때문에 O(logN)이다. 하지만, 이진 탐색은 정렬된 배열에서만 사용할 수 있기 때문에 상충관계 (trade-off)가 있다. 모든 것에는 trade-off가 있기 마련이다.

(2) 최선, 평균, 최악의 경우

이진탐색은 최악의 경우에도 O(logN)의 시간복잡도를 보장한다. 참고로 위의 코드에서는 이진탐색을 반복문으로 구현했는데, 검색 범위를 절반으로 줄이는 부분을 재귀 호출로 구현할 수도 있다. 근데 이렇게 하면 함수 호출로 인해 공간 복잡도가 더 늘어나므로 반복문을 사용하는 것이 더 좋다. (함수 호출에는 매개변수, 리턴값, 리턴 주소 등을 저장하기 위한 메모리 공간이 필요하다.)

참고 자료

https://youtu.be/IfIuG95RH0o
https://youtu.be/WjIlVlmmNqs
https://youtu.be/BEVnxbxBqi8
https://library-of-k.tistory.com/3