이진 탐색
정렬 되어있는 리스트에서 특정한 데이터를 빠르게 탐색할 수 있도록 해주는 알고리즘
순차 탐색 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법
이진 탐색 정렬된 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
재귀함수과 반복문으로 풀 수 있다
파이썬 이진 탐색 라이브러리
bisect_left(a,x): 정렬된 순서를 유지하면서 배열 a에 x 를 삽입할 가장 왼쪽 인덱스를 반환
bisect_right(a,x): 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스를 반환
값이 특정 범위에 속하는 데이터 개수 구하기를 쉽게 가능
right에서 left를 빼면됨
파라메트릭 서치 (parametric search)
최적화 문제를 결정 문제(예 혹은 아니요)로 바꾸어 해결하는 방법
큰 탐색 범위를 보면 이진 탐색을 떠올려야 한다
