[Python] bisect_left 구현

아이고

이진탐색문제를 푸는데 bisect없이 풀어 보겠다고 도전했지만 보기 좋게 실패했다. 그래서 공부도 하고 라이브러리 의존도를 낮추기 위해 파이썬의 bisect의 bisect_left를 구현했다.

구조

bisect에는 대표적으로 bisect_left와 bisect_right가 있다.
bisect_left와 bisect_right는 둘 다 배열에서 value가 들어갈 수 있는 적절한 위치를 반환하는 함수이다.

규칙

두 함수는 이진탐색을 할 때 이러한 규칙을 가진다.
bisect_left : value < arr[index]
bisect_right : value > arr[index]

예시

배열에 10 20 30 40 50 있다고 하자. 이 배열에서 25가 들어갈 위치를 찾을 때 배열 안에 같은 값이 없다면 index는 arr[index-1] < value < arr[index + 1]이 성립해야 한다.
그래서 bisect_left와 bisect_right는 2로 같은 값을 반환한다.
하지만 30의 들어갈 위치를 찾을 때 두 함수는 위에 적은것과 같은 규칙을 적용하기 때문에 bisect_left는 2를 bisect_right는 3으로 다른 값을 반환한다.

---

기존코드

def binary_search(lst, value):  
    lp = 0  
    rp = len(lst) - 1  
    cp = 0  
    while lp < rp:  
        cp = (lp + rp) // 2  
        if lst[cp] == value:  
            return cp  
        if lst[cp] < value:  
            rp = cp - 1  
        else:  
            lp = cp + 1  
    if cp == 0:  
        return cp  
    if lst[cp-1] > value:  
        return cp - 1  
    else:  
        return cp

기존 코드는 중간 값을 리턴하는 형태이다. 중간값이 비교값보다 작으면 오른쪽 포인터를 중간에서 -1을 비교값보다 크다면 왼쪽 포인터를 중간값 + 1을 한다. 만약 같은값을 찾지 못하면 현재 cp인덱스의 앞과 뒤를 확인하여 적절한 값을 찾는 코드이다.
사실 이 코드에는 몇가지 해결해야 할 문제가 있다.

1. 일치하는 위치가 배열의 첫번째 또는 마지막에 위치한다면?
2. while안에서 해결하지 못했다는 것은 배열안에 value와 같은 값이 없다는 건데 현재 cp가 적절한 위치가 맞는가?
   이러한 문제들이 있어 bisect라이브러리를 보고 수정했다.

수정코드

def binary_search(lst, value):  
    lp = 0  
    rp = len(lst)  
    while lp < rp:  
        cp = (lp + rp) // 2  
        if lst[cp] < value:  
            lp = cp + 1  
        else:  
            rp = cp  
    return lp

수정한 코드는 배열의 처음부터 마지막까지 확인이 가능하며 일치하는 값이 있다면 lp가 일치하는 값을 반환한다.

관련 문제 : 875. Koko Eating Bananas

참고 : 공식문서