[알고리즘] 이진탐색

정의

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

코드 구현

def binary_search(array, target, start, end):
    if start > end:
        return None
    mid = (start + end) // 2
    if array[mid] == target:
        return mid
    if array[mid] > target:
        end = mid - 1
    else:
        start = mid + 1
    return binary_search(array, target, start, end)


target = 3
array = [5, 4, 2, 1, 3]
result = binary_search(array, target, 0, len(array))
if result == None:
    print('not found index')
else:
    print('found index : {}'.format(result + 1))