[Python][알고리즘] 이진 탐색

(나동빈 님의 위 영상을 바탕으로 정리한 내용입니다.)

---

이진 탐색 구현 (반복문 ver)

def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        
        if array[mid] == target:
            return mid
            
        elif array[mid] > target:
            end = mid - 1
            
        else:
            start = mid + 1
            
    return None

bisect 모듈

• bisect_left(a, x)
  정렬된 배열 a에서 x가 들어갈 가장 왼쪽 인덱스를 반환

• bisect_right(a, x)
  정렬된 배열 a에서 x가 들어갈 가장 오른쪽 인덱스를 반환

특정 범위에 속하는 데이터의 개수 구하기

bisect_left() 메서드와 bisect_right() 메서드를 활용하여 구할 수 있다.

from bisect import bisect_left, bisect_right

def count_by_range(array, left_value, right_value):
    l_index = bisect_left(array, left_value)
    r_index = bisect_right(array, right_value)
    return r_index - l_index