[D&C] Binary Search

이진 탐색

정렬된 A[0...n-1]의 배열에 대해 k값을 찾을 때, a의 중간값(median)을 k 와 비교하여 같으면 종료.

 

이진탐색은 실은 분할정복기법이다. 중간값을 k와 비교한 뒤에 배열의 절반에 대해서만 탐색을 계속한다.

즉 문제의 크기가 n/2인 동일한 작은 문제를 해결하다보면, 문제를 해결 할 수 있다.

 

이진탐색

By AlwaysAngry - 자작, CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php?curid=53687795

 

# A가 정렬된 배열일때 A[a...b]에서 k값을 탐색
int binary_search(A[a...b], k, a, b):
	if a>b:
    	return -1
    mid = (a+b)/2
    if A[mid] > k:
    	return binary_search(A, k, a, mid-1)
    elif A[mid] < k:
    	return binary_search(A, k, mid+1, b)
    else return mid

 

시간 복잡도 : O(logn)

점화식 : T(n) = T(n/2) + O(1)