오름차순으로 정렬된 배열에서 찾고자 하는 수(target)를 두 부분으로 나눠서 찾는 알고리즘 기법
순차 탐색(Linear Search)보다 더 빠른 성능을 보인다.
- 탐색 리스트가 정렬되어 있지 않으면 정렬
- left(리스트 첫번째), right(리스트 마지막), mid(리스트의 중간 값)을 잡는다.
: 값보단 리스트의 인덱스로 잡는 것이 더 범용적으로 사용할 수 있다.- mid 값과 찾고자 하는 target 값을 비교
- mid 값이 더 크면 rigth값을 mid-1로, mid 값이 더 작으면 left 값을 mid+1로 세팅
- left > right가 될 때까지 반복
탐색이 계속 1/2씩 줄어들기 때문에 시간 복잡도는 O(logN)이다.
def binary_search(arr, value):
left, right =0, len(arr)
while left <= right:
mid = (left+right) //2
if arr[mid] == value:
return mid
if arr[mid] > value:
right = mid -1
else:
left = mid +1
return None
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
result_index=binary_search(arr, 3)
print(result_index, arr[result_index])
def binarySearch(array, target, left, right):
if left > right:
return None
mid = (left+right) //2
if target == array[mid]:
print(mid)
# return mid
elif array[mid] > target:
binarySearch(array, target, left, mid-1)
else:
binarySearch(array, target, mid+1, right)
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
arr.sort()
binarySearch(arr, 3, 0, len(arr))