이진 탐색

[Algorithm] 이진 탐색(Binary Search) 알고리즘

Binary Search Idea 이진 탐색은 정렬된 배열이 주어질 때, 리스트의 중간값과 비교하면서 반씩 제외하며 원하는 값을 찾아가는 과정입니다. 주의할 점은, 이진 탐색 알고리즘은 정렬된 배열에만 적용 가능하다는 점입니다. 따라서 정렬되어있지 않다면 성능이 우수한 퀵 정렬을 통해 약 O(nlogn)의 시간을 들여 정렬을 한 뒤 이진 탐색 알고리즘을 적용해야 합니다. 이진 탐색의 과정을 살펴보면 아래와 같습니다. 중간 인덱스(middle)를 구한다. (첫번째 인덱스 + 마지막 인덱스) / 2 찾을 값(target)이 middle보다 작은 경우, middle과 그 이후 인덱스들을 검색 범위에서 제외한다. target이 middle보다 큰 경우, middler과 그 이전 인덱스들을 검색 범위에서 제외한다..