이진 탐색 알고리즘

• 순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법

• 이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
  -이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정합니다.

  이진 탐색은 시간 복잡도 O(log N)을 보장한다.

  코드 예시)

1. while 반복문 사용
   

2. 재귀 함수 사용
   

이와 같이 while 문과 재귀함수 둘다 사용할 수 있다.

라이브러리

• from bisect import bisect_left, bisect_right

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

이를 응용하여 값이 특정 범위에 속하는 데이터 개수를 구할수있다.

코드 예시)

• 파라메트릭 서치) 란 최적화 문제를 결정문제(예, 아니오)로 바꾸어 해결하는 기법이다.
  예시) 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제