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

[알고리즘 소개]

배열 내에서 특정 요소 k를 $O(logn)$으로 찾는 알고리즘.

 

---

[알고리즘 특징]

배열을 미리 정렬 해야 함.

 

---

 

[코딩 방법]

1. 배열 arr을 정렬. 결과 인덱스 idx = N으로 설정(일치하는 값이 없는 경우 lower bound를 출력하기 위함).
2. 최소 인덱스 0부터 최대 인덱스 N - 1까지의 중간값 mid를 구함
3. left는 0부터, right는 N - 1부터 시작해서 left <= right인 경우 반복문
4. 표적 k와 arr[mid]를 비교, arr[mid] >= k면 idx = mid, right = mid - 1; else left = mid + 1
5. idx가 lower bound이면서 결과 인덱스가 됨.

---

[응용]

k 이상이 처음 나오는 lower bound, k 초과가 처음 나오는 upper bound.

꼭 배열이 아닌 구간에 대해 실행해도 됨. (나무 자르기)

 

---

[시간 복잡도]

 

$O(logn)$