자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 진행하는 방법입니다.
목적 값을 찾을 때까지 이진 검색을 순환적으로 반복 수행함으로써 검색 범위를 반으로 줄여가면서 보다 빠르게 검색을 수행하는 탐색 방법으로써 주의해야 될 사항은 이진 검색을 하기 위해서는 자료의 형태가 정렬된 상태여야 합니다.
def binarySearch(a, key):
start = 0
end = len(a)-1
while start <= end:
middle = (start + end)//2
if a[middle] == key : # 검색 성공
return True
elif a[middle] > key:
end = middle -1
else: start = middle + 1
return False # 검색 실패
다음은 재귀 호출 방법으로 이진 탐색을 구현해 보겠습니다.
def binaryRecursive(a, low, high, key) : #재귀호출
if high < low : # 검색 실패, 재귀 탈출
return False
else:
middle = (low + high) // 2
if key == a[middle]: #검색 성공
return Ture
elif key < a[middle] :
return binarySearch2(a, low, middle-1, key)
elif a[middle] < key:
return binarySearch2(a, middle+1, high, key)
이진 탐색은 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있습니다. 하지만 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 정렬되어 있는 경우 순차 탐색(Sequential Search)보다 속도가 빠를 수 있다는 장점이 있어 여러모로 편리한 방법인 것 같습니다.