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

이진 탐색의 시간 복잡도

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

이진 탐색 라이브러리 추천

파라메트릭 서치 (Parametric Search)

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