bisect - binary search

참조 : 

programmers.co.kr/learn/courses/4008/lessons/13173

programming119.tistory.com/196

[Python] bisect 사용법👀 / 이분탐색 / 코딩테스트

파이썬을 파이썬답게 - 이진 탐색하기 - binary search

---

■ 이진탐색

1) 정의 :

- O(logN) 비례

 

> 원본 구현 방법

# python 공식 문서
#################
def bisect(a, x, lo=0, hi=None):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo

mylist = [1, 2, 3, 7, 9, 11, 33]
print(bisect(mylist, 3))


# hard coding
#################
def binary_search(target, data):
    data.sort()
    start = 0
    end = len(data) - 1

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

        if data[mid] == target:
            return mid # 함수를 끝내버린다.
        elif data[mid] < target:
            start = mid + 1
        else:
            end = mid -1

    return None

 

> bisect 함수

1) 사용 방법 :

bisect_left(literable, value) : 왼쪽 인덱스를 구하기 == 시작 index
bisect_right(literable, value) : 오른쪽 인덱스를 구하기 == 끝 index + 1 →  bisect.bisect( ) 와 동일

import bisect

mylist = [1, 2, 3, 3, 7, 9, 11, 33]

print(bisect.bisect_left(mylist, 3))
print(bisect.bisect(mylist, 3))
print(bisect.bisect_right(mylist, 3))

>>>
2
4
4