[c++] Binary Search, 이진탐색

이진탐색이란?

이진탐색은 이미 정렬된 배열에서, 특정한 숫자를 찾는 정렬 알고리즘이다. 찾고자하는 숫자를 배열의 중간값과 비교하여, 만약 작다면 왼쪽을 다시 탐색, 크다면 오른쪽을 다시 탐색하면서 숫자를 찾아낸다. 원하는 값을 찾아내면 탐색은 종료되며, 존재하지 않는다고 판단하여도 탐색을 종료한다. 존재하지 않는다고 판단하는 기준은 탐색할 인덱스가 없을때 이다. 구현방법은 반복문을 사용할 수도 있고, 재귀를 사용할 수도 있는데 아래의 코드는 재귀를 사용하여 구현한 것이다. 

Binary Search - GeeksforGeeks

  

구현코드

int binarySearch(int arr[], int l, int r, int x) {
	if (r >= l) {
		int mid = l + (r - l) / 2;
		if (arr[mid] == x)
			return mid;
		if (arr[mid] > x)
			return binarySearch(arr, l, mid - 1, x);

		return binarySearch(arr, mid + 1, r, x);
	}
	return -1;
}

 

주의할점 

사실 많은 코드에서 중간값을 (low+high)/2 로 선정을 하는데, 이럴 경우 버그가 생길 수 있다. low와 high가 매우 큰값으로 선정이 되는 경우에는, low+high가 int MAX를 초과할 수 있다. 따라서 이 경우를 대비하여 중간값을 low+(high-low)/2 로 선정을 해주어야 버그를 막을 수 있다. 

 

시간복잡도

O(log n)이다. n크기의 배열에서 1/2로 크기가 점점 줄어들기 때문에 log2 n의 시간복잡도를 가진다.