이진 탐색

• 순차탐색 : 순차적으로 탐색
• 이진탐색 : 정렬되어 있는 리스트에서 탐색범위를 절반씩 좁혀가며 탐색
  • 연산 횟수 : $log_2N$에 비례 -> 시간 복잡도는 $O(logN)$을 보장

반복문 구현

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 

파이썬 이진 탐색 library

: 정렬된 리스트에 값을 삽입할 때 정렬을 유지할 수 있는 인덱스를 리턴

• bisect_left(a,x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스를 반환
• bisect_right(a,x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스를 반환

EX.

from bisect import bisect_left, bisect_right

a = [1, 2, 4, 4, 8]
x = 4
print(bisect_left(a, x))
print(bisect_right(a, x))

실행결과 :
2
4

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

from bisect import bisect_left, bisect_right

def cbr(a, left,right):
    right_index = bisect_right(a, right)
    left_index = bisect_left(a, left)
    return right_index - left_index 

Parametric Search

: 최적화 문제를 결정문제(Y or N)로 바꾸어서 해결하는 기법 => 이진탐색으로 해결 가능