[알고리즘] 이진 탐색 (Binary search)

이진 탐색 알고리즘 (Binary search)

배열이 오름차순으로 정렬되어 있다는 가정 하에 특정한 값을 검색하는 알고리즘이다.

int binarySearch(int data[], int target, int begin, int end) {
	if (begin > end)
		return -1;
	else {
		int middle = (begin + end) / 2;
		if (data[middle] == target)
			return middle;
		else if (data[middle] > target)
			return binarySearch(data, target, begin, middle - 1);
		else
			return binarySearch(data, target, middle + 1, end);
	}
}

처음 중간값(middle)을 임의로 선택한 후, 만약 찾고자 하는 값이 중간값보다 크다면 2등분으로 분할한 배열에서 왼쪽으로 이동한다. 또, 분할된 배열의 중간값을 선택한 후 찾고자 하는 값의 위치에 따라 왼쪽, 오른쪽으로 이동할 지를 결정한다. 위는 순환함수로 작성된 이진 탐색 알고리즘이다.

순차검색의 시간 복잡도는 $O(n)$인 것에 비해 이진검색의 시간 복잡도는 $O(log n)$으로 이는 매우 큰 실행속도의 차이이다.

다만 이진탐색의 전제조건은 오름차순으로 정렬된 배열이라는 점에 유의한다. 순서가 없는 연결리스트의 경우엔 이진탐색을 할 수 없다.

참고자료
https://www.geeksforgeeks.org/binary-search/