[알고리즘] 이진 검색 알고리즘(binary search algorithm)

1. 이진 검색 알고리즘이란

정렬되어있는 리스트에서 특정한 값의 위치를 찾는 알고리즘으로

찾고자 하는 값이 중간 값보다 크면 중앙값(또는 중앙값 +1)이 새로운 최솟값이 되어 다시 값을 찾는다

검색이 반복될 때마다 목표값을 찾을 확률이 두 배가 된다.

 

업다운 게임과 알고리즘의 형태가 비슷하다고 생각한다

 

2. python 코드

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

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 13, 15]

print(binarySearch(arr, 4))
print(binarySearch(arr,12))

True
False

4는 배열 안에 있기 때문에 True 12는 배열에 존재하지 않기 때문에 False를 반환한다

 

이진탐색 코드는 반드시 '정렬된 리스트'에서 실행되어야 한다.