Binary search, 이진 탐색

리스트 A = [ 0, 1, ,2, 3 ] 이 있을 때, 마지막 원소인 '3'을 찾는다고 해보자.

Simple search, 단순 탐색의 경우 처음부터 순차적으로 원소 값을 확인한다. 마지막에 위치하고 있는 원소인 '3'을 찾기 위해서는  리스트의 길이와 같은 시간이 걸린다. 리스트의 길이와 같은시간을 O(n), linear time 선형시간 이라고 한다.

Binary search, 이진 탐색은 리스트의 중간에 있는 원소의 크기에 따라 탐색할 구간(range)를 반씩 줄여나가 O(log n), logarithm time 로그 시간이 걸리는 방식이다. 만약 100개의 원소를 가지고 있는 리스트라면 탐색할 구간이 100 에서 50, 25, 13, 7, 4, 2, 1 순으로 줄어든다. 따라서, A의 중간에 위치한 A[2] 위치의 원소인 '2'은 찾고자하는 원소인 '3'보다 작으므로 구간 A[:3] = [ 0, 1] 은 버려지고, 다음 iteration에서는 A[3:] = [3]이 탐색되는 구간이다.

Binary search 파이썬 구현 (* 이진 탐색은 탐색할 리스트가 이미 정렬되어 있을 때를 가정한다.)

'''
INPUT: A = sorted array, i = value want to fine
OUTPUT: If value i is in A, return the index of it,
        if not return -1.
low = 탐색 범위 맨 앞 인덱스
high = 탐색 범위 맨 끝 인덱스
'''

def binarySearch(A,i):
    low = 0
    high = len(A) -1
    while low <= high:
        mid = (low + high) // 2
        if A[mid] == i:
            return mid
        elif A[mid] < i:
            low = mid+1
        else:
            high = mid
    return -1