binary search

• 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘
• 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식

• 검색속도가 아주 빠른 것이 특징
• 정렬된 리스트에서만 사용할 수 있다는 단점

• 시간복잡도
  • 최선: O(1)
  • 평균: O(log N)
  • 최악: O(log N)

이진탐색 알고리즘 구현

• 직접 반복문을 통해 이진탐색 알고리즘 구현

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))

• bisect 를 사용하여 알고리즘 구현

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

bisect

• 정렬된 배열의 요소에서 삽입 위치를 찾거나, 특정 범위 내의 요소들을 검색하는데 사용
• 이진 검색 알고리즘을 사용하여 효율적으로 작동
• bisect_left(), bisect_right() (bisect.bisect())함수가 있음

import bisect

a = [1, 2, 4, 5]
x = 3

# x를 a에 삽입할 위치를 찾습니다.
pos = bisect.bisect_left(a, x)
print('bisect_left:', pos)  # x를 삽입할 가장 왼쪽 위치 출력

pos = bisect.bisect_right(a, x)
print('bisect_right:', pos)  # x를 삽입할 가장 오른쪽 위치 출력

# 실제로 x를 리스트에 삽입하지 않고 위치만 찾는 예제입니다.
# x를 실제로 삽입하려면 a.insert(pos, x)를 사용할 수 있습니다.

• bisect는 정렬된 시퀀스 내에서 지정된 요소를 삽입할 때 해당 요소가 들어갈 수 있는 가장 오른쪽 인덱스를 반환

import bisect

a = [1, 2, 4, 4, 5]
x = 4

# x를 a에 삽입할 위치를 찾습니다.
pos = bisect.bisect(a, x)  # bisect_right와 동일합니다.
print('Insert position:', pos)  # 출력: 5

---

참고
--

• https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%EA%B2%80%EC%83%89_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98