[파이썬/python] 이진 탐색 (Binary Search)

이진 탐색이란 오름차순으로 정렬된 배열에서 원하는 숫자를 찾는 알고리즘이다.

반드시 정렬된 상태에서 시작해야하고 로그실행시간(O(log N))을 보장한다.

 

• target : 찾을 값
• start : 시작 인덱스
• end : 마지막 인덱스
• pivot : 중간 인덱스

위 4가지를 이용하여 구현한다.

리스트의 중간 인덱스 pivot 값이 찾고자하는 값 target과 같은지 비교하면서 진행된다.

같지 않다면 start 값과 end 값을 적절히 조절하여 pivot 값을 바꿔가며 다시 target과 비교한다.

위를 반복하면 반복할 때마다 범위가 반씩 줄어들게되므로 logN의 시간을 갖는다.

 

예를 들어 1부터 10까지의 수 중 target 8을 찾으려 한다.

1을 start로 10을 end로 설정하고 그 중간 값인 5를 pivot으로 설정한다.

5와 8이 같지 않으므로 start 값을 pivot보다 크게 조절하여 범위를 줄인다.

 

start를 6으로 바꾸고 end는 그대로 10으로 설정한다. 그럼 그 중간 값인 8이 pivot이 된다.

pivot 8과 target 8이 같으므로 이진탐색이 끝난다.

 

파이썬으로 구현하기

while end >= start:
        pivot = (end + start) // 2
        
        if pivot < target:   
            start = pivot + 1

        elif pivot > target: 
            end = pivot - 1

        else:
            break

end값과 start값이 계속 바뀌므로 start 값이 end 값을 넘지 않을 때까지 반복한다.

pivot을 중간값으로 잡아주고 target과 비교한다.

만약 pivot 값이 더 작다면 target의 예상 가능한 최소값은 pivot +1이므로 start를 pivot + 1로 설정한다.

만약 pivot 값이 더 크다면 target의 예상 가능한 최대값은 pivot - 1이므로 end를 pivot - 1로 설정한다.

pivot 값과 target 값이 같다면 break를 통해 반복문을 빠져나간다.