[Python] 이진 탐색(Binary Search)

N개의 정렬된 숫자가 있으면

숫자의 개수를 반씩 줄여나가면서 원하는 숫자를 찾는 탐색 방법이다.

 

이진 탐색의 시간 복잡도 : O(logN)

 

 

<기본 코드>

target의 인덱스를 찾아라.

def binarySearch(data, target):
    start = 0
    end = len(data)-1

    while start <= end:
        mid = (start + end) // 2

        if data[mid] < target : start = mid + 1
        elif data[mid] > target : end = mid - 1
        else : return mid

    return -1

<실행 결과>

 

 

 

 

내가 찾는 수가 리스트에 없을 경우

end의 초기값과 while이 실행되는 조건, whlie문 안에 if-else문이 달라진다.

 

 

<lower bound>

target보다 크거나 같은 수가 시작되는 인덱스를 찾아라.

def binarySearch_lower(data, target):
    start = 0
    end = len(data)

    while start < end:
        mid = (start + end) // 2

        if data[mid] < target : start = mid + 1
        else : end = mid

    return end

<실행 결과>

<실행 결과>

 

 

<upper bound>

target보다 큰 수가 시작되는 인덱스를 찾아라.

def binarySearch_upper(data, target):
    start = 0
    end = len(data)

    while start < end:
        mid = (start + end) // 2

        if data[mid] <= target : start = mid + 1
        else : end = mid

    return end

<실행 결과>

<실행 결과>