이진탐색

이진탐색

정렬되어 있는 리스트에서 탐색 범위를 좁혀가며 데이터를 탐색하는 방법.
시작점과, 끝점, 중간점을 이용하여 탐색 범위를 설정한다.

정렬이 되어있는 리스트에서 작동하기 때문에 탐색전 정렬이 필요하다

코테에서는 보통 데이터의 개수가 1000만개를 넘어가거나 탐색 범위의 크기가 2000만 이상이라면 이진 탐색을 의심해볼만 하다. O(logN)으로 풀어야 하는 경우임

그리고,

파라메트릭 서치란 최적화 문제를 결정문제로 바꾸어 해결하는 기법이다.
ex) 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제 - 절단기 문제(현재 높이로 자르면 조건을 만족할 수 있는가? - 절단기의 크기를 범위내에서 이진탐색)
-> 이진탐색을 이용하여 해결할 수 있다.