이분 탐색 - goorm-6th-Als/for_study_Algorithm GitHub Wiki
이분 탐색 = 이진 탐색(Binary Search)
이분 탐색은 정렬된 배열 또는 리스트에 적합한 탐색 방법이다.
- 배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는지를 알아내어 탐색의 범위를 반으로 줄인다.
- 찾고자 하는 값이 속해있지 않은 부분은 전혀 고려할 필요가 없기 때문에, 매 단계에서 검색해야 할 리스트의 크기를 반으로 줄일 수 있다.
- 이러한 방법을 반복적으로 사용해 탐색하는 방법이 이분 탐색이다.
- 데이터의 삽입이나 삭제가 빈번할 시에는 적합하지 않고, 주로 고정된 데이터에 대한 탐색에 적합하다.
ex 1) 10억 명이 정렬된 배열에서 이분 탐색을 이용해 특정 이름을 찾는다면 단 30번의 비교만으로 검색이 완료된다.
반면에 순차 탐색의 경우 평균 5억 번의 비교가 있어야 된다.
ex 1-1) 9개의 숫자 중 82를 찾는 경우 3번만에 탐색가능
ex 2) 영어 사전에서 단어를 찾는 과정 역시 이분 탐색과 동일하다.
영어 사전을 펼쳐서 찾고자 하는 단어가 현재 페이지에 있는 단어보다 앞에 있는지, 뒤에 있는지를 결정한 다음,
단어가 있는 부분 만을 다시 검색한다.
시간 복잡도는 O(log n)