이진 탐색(Binary Search)

이진 탐색 알고리즘은 1회 비교를 거칠 때마다 탐색 범위가 (대략) 절반으로 줄어드는 알고리즘

정렬된 리스트가 아니면 사용불가

def binary_search(element, some_list):
    start_index = 0
    end_index = len(some_list) - 1

    while start_index <= end_index:
        midpoint = (start_index + end_index) // 2
        # 찾고자하는 값이 앞쪽에 있음
        if some_list[midpoint] > element:
            end_index = midpoint - 1
        # 찾고자하는 값이 뒤쪽에 있음
        elif some_list[midpoint] < element:
            start_index = midpoint + 1
        # 찾고자하는 값이 리스트의 중간값이랑 같을때
        else:
            return midpoint
    return None;

리스트의 길이가 16일때 

가장빨리 찾는 방법은 맨 처음 원소를 찾을때 1번의 연산(가운데 값을 바로 찾음)

가장오래 걸리는 방법은 리스트 내에 원소가 없을때 총 4번의 연산

-> 16 / 2(1회)

-> 8 / 2(2회)

-> 4 / 2(3회)

-> 2 / 2(4회)