Work, Study/코테, 알고리즘

[Python] 이진 탐색

Waltwaez 2024. 7. 24. 21:17

이진 탐색은 일반적으로 이렇게 짠다.

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1


1. 종료 조건

- 종료 조건은 인덱스가 left > right일 때이다. (즉 반복 조건은left <= right )

- left < right로 반복 조건을 짤 경우, left == right 가 되면, 찾고자 하는 값이 배열에 없을 경우 무한 루프에 빠질 수 있다.

 

 

2. 갱신 조건

위처럼 left, right 를 갱신하는 게 일반적이지만..

 

2.1. 중복 값중 가장 왼쪽/오른쪽 인덱스 찾기

중복된 값 중 가장 왼쪽을 찾고 싶거나, 가장 오른쪽을 찾고 싶은 경우는 아래처럼 구현한다.

공통적으로 left < right (기존에는 left <= right )
가장 왼쪽 찾기 : right 갱신 조건에서 mid - 1 대신 mid 
가장 오른족 찾기 : left 갱신 조건에서 mid + 1 대신 mid 

 

가장 왼쪽 인덱스 값 찾기

    while left < right: 
        mid = (left + right) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid

    return left if arr[left] == target else -1

 

 

가장 오른쪽 인덱스 값 찾기

    while left < right:
        mid = (left + right + 1) // 2
        if arr[mid] > target:
            right = mid - 1
        else:
            left = mid

    return left if arr[left] == target else -1