순차 탐색

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

이진 탐색

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

• 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다.

• 동작 예시

• 시간 복잡도

  

• Python 코드

• Python의 이진 탐색 라이브러리

파라메트릭 서치 (Parametric Search)

• 파라메트릭 서치란 최적화 문제를 결정 문제(’예’ 혹은 ‘아니오’)로 바꾸어 해결하는 기법이다.
  • 예시: 특정한 조건을 만족한느 가장 알맞은 값을 빠르게 찾는 최적화 문제
• 일반적으로 코딩 테스틀에서 파라메트릭 서치 문제는 이진 탐색을 이용하여 해결할 수 있다.