이진탐색

사람들이 즐기는 업앤다운 게임을 생각하면 이해하기 쉽다. 업앤다운 게임은 출제자가 숫자 하나를 선정하면 나머지 사람들은 숫자를 유추하고 출제자는 유추한 숫자가 선정된 숫자보다 작은지 큰지를 알려주며 점점 범위를 좁혀나가 숫자를 알아맞추는 게임이다. 이진탐색도 마찬가지로 정렬된 숫자배열에서 중간값을 찾고 찾으려는 값이 중간값보다 작은지 큰지를 비교하며 점점 범위를 좁혀나가며 숫자를 찾는 방식이다.

• 이진탐색코드예제

# 1~10까지 순서대로 담긴 list가 존재하고 여기서 8을 찾아내는 이진탐색 코드
def solution(list):
    left=0
    right=len(list)-1
    while(left<=right):
        mid=(left+right)//2
        if list[mid]==8:
            return mid
        elif list[mid]<8:
            left=mid+1
        elif list[mid]>8:
            right=mid-1
    return mid