이진 탐색 (Binary Search)

 이진 탐색은 정렬된 배열에서 탐색 시간을 줄이기 위한 알고리즘이다. 배열 안에서 어떤 원소 E를 찾을 때, 단순 선형 탐색으로 구현할 경우 O(N) 시간이 걸린다. 하지만 이진 탐색을 수행하면 O(log N) 시간에 수행할 수 있다. 

 

출처 : https://www.programiz.com/dsa/binary-search

 위 그림과 같이 크기가 7인 배열이 존재하고, 이 배열은 오름차순으로 정렬되어있다. 인덱스는 0부터 시작하여 6까지 존재하게 된다. 이진 탐색은 정렬된 배열의 가운데와 구해야 하는 원소를 비교하여 절반만큼 비교 범위를 줄여나가는 것이다. 위 그림에서 mid = (low + high) / 2 를 구하면, (0 + 6) / 2 = 3이고, 3번 인덱스의 값인 6과 비교하게 된다. 만약 구해야 하는 숫자 M = 7이라고 가정하자. 7은 mid보다 크므로, [low = mid + 1 = 4, high = 6] 구간에 대해서 이진 탐색을 재귀적으로 수행한다. mid = (4 + 6) / 2 = 5이고, 5번 인덱스의 값은 8이므로 M = 7보다 작다. 따라서 이번에는 high = mid로 설정하고 [low = 4, high = mid = 5]에 대하여 다시 한번 수행한다. mid = (4 + 5) / 2 = 4.5 = 4 이므로 4번 인덱스의 값인 7과 비교하면 원하는 원소를 찾아낼 수 있다. 

 

 이진 탐색에서 가장 중요한 것은 루프를 탈출하는 base case의 설정이다. 만약 low > high 가 탈출 조건이 될 경우, 한 원소 내에서 무한 루프를 돌 수 있다. c++에서 정수끼리의 나눗셈 연산은 소수점을 그냥 버리게 되는데, 이는 구간을 다르게 설정하는 mid = (low + high) / 2에서 같은 값을 계속 도출하게 만들 수 있다. low == high의 경우에는 트리에서 마치 리프 노드에 도달한 것과 같다. 나의 경우에는 이 경우에 구하는 값과 현재 값이 일치한지 확인하고 일치하면 true를, 일치하지 않으면 false를 리턴하는 방식으로 구현했다.

 

bool binary_search(int start, int end, int num) {
	int mid = (start + end) / 2;

	if (start == end) {	// base case
		if (arr[start] == num) {
			return true;
		}
		else {
			return false;
		}
	}

	if (arr[mid] == num) {
		return true;
	}
	else if (arr[mid] > num) {
		return binary_search(start, mid, num);
	}
	else {
		return binary_search(mid + 1, end, num);
	}
}

 이진 탐색의 경우 정렬되어있는 배열의 중간 인덱스의 값이 구하려는 값보다 작거나 크면 그에 반대되는 나머지 부분은 탐색할 필요가 없다는 점을 이용한 알고리즘이므로 반드시 배열이 정렬되어있어야 한다. 이진 탐색을 이용한 알고리즘은 매우 다양하지만, 매우 밀접한 연관이 있는 매개변수 탐색(Parametric Search)에 대해 다음에 소개하도록 하겠다.