이진 탐색 (Binary Search)
정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
🔥 배열 내부의 데이터가 꼭 정렬되어 있어야 함!
이진 탐색 vs 순차 탐색
변수 3개(start, end, mid)를 사용하여 탐색한다.
찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색의 과정이다.
시간 복잡도
이진 탐색 : O(lonN)
순차 탐색 : O(N)
예제
땅콩의 모험 (server)