- 순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법
- 이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
- 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정합니다.
- 로그 시간 복잡도를 가지게 됨




이진 탐색의 시간 복잡도
- 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 log2(N) 에 비례한다.
- 예를 들어 초기 데이터 개수가 32개일 때, 이상적으로 1단계를 거치면 16개 가량의 데이터만 남음
- 2단계에서는 8개, 3단계에서는 4개 가량의 데이터만 남음.
- 다시 말해 이진 탐색은 탐색 범위를 절반씩 줄이며 시간 복잡도는 O(logN)을 보장

이진 탐색 라이브러리 추천


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