[알고리즘] 이진 탐색(Binary Search)이란?

이진 탐색(Binary Search)

- 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘

- 처음 중간의 값을 임의의 값으로 선택하고 찾고자 하는 값의 크고 작음을 비교하는 방식

- 처음 선택한 중앙값이 찾는 값보다 크면 그 값은 최댓값이 되며, 작으면 최솟값이 됩니다.

 

 

장점

검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠릅니다.

 

단점

검색 원리상 정렬된 리스트에만 사용할 수 있습니다.

 

구현 예시(Python)

def binarySearch(array, value, low, high):
    if low > high:
        return False
    mid = (low+high) // 2
    if array[mid] > value:
        return binarySearch(array, value, low, mid-1)
    elif array[mid] < value:
        return binarySearch(array, value, mid+1, high)
    else:
        return mid

target = 30
array = [7, 23, 27, 30, 44, 78, 21, 9, 13, 66, 11, 45]
length = len(array)

array.sort()
low = 0
high = length-1

print(f'array = {array}')
print(binarySearch(array, target, 0, high))

array = [7, 9, 11, 13, 21, 23, 27, 30, 44, 45, 66, 78]
7