이진 탐색 알고리즘

이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법

• 시간 복잡도 : O(logN)

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

from bisect import bisect_left, bisect_right

#값이 left_value, right_value 사이에 있는 데이터의 개수를 반환하는 함수 

def count_by_range(a, left_value, right_value):
    left_index = bisect_left(a, left_value)
    right_index = bisect_right(a, right_value)
    return right_index - left_index

파라메트릭 서치

최적화 문제를 결정 문제(예, 아니오)로 바꾸어 해결하는 기법

• 예시) 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제
• 일반적으로 코테에서 파라메트릭 서치 문제는 이진탐색으로 해결함