이진 탐색(binary search)

이진탐색

'정렬된 리스트'에서 특정 값을 빠르게 찾는 알고리즘.
리스트를 반으로 나눠서 목표값이 어느 쪽 절반에 속하는지 결정하고, 나머지 절반은 버리면서 목푯값이 포함될 가능성이 있는 절반을 탐색한다.
값을 찾을 때까지 이 과정을 반복한다. 어느 쪽에 속해야하는 지 결정해야하기 때문에 기본적으로 정렬된 리스트여야한다.

배열 A 에서 i < j 인 모든 i, j 인덱스 쌍에 대해
A[i] <= A[j]를 만족하면 배열 A 는 오름차순으로 정렬된 배열이다.

문제 정의

다음과 같은 오름차순으로 정렬된 배열 A 가 있다.
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

이 배열 A 에서 숫자 10을 찾아보자.

문제 해결

앞서 말한 것처럼 이진 탐색은 리스트를 반으로 나누어 탐색하기 때문에 탐색공간의 중앙값을 선택하며 시작해야한다. 이를 코드로 나타내면 다음과 같다.

var indexHigh = list.size - 1 // 탐색공간의 최대 index
var indexLow = 0  // 탐색공간의 최저 index

val indexMid = floor((indexLow + indexHigh) / 2.0).toInt() // 중앙 Index
...

이제 탐색을 시작해보자.

첫 번째 탐색

indexHigh == 9
indexLow == 0
indexMid == 4

A[4] == 5 != 10

두 번째 탐색

indexHigh == 9
indexLow == 5
indexMid == 7

A[7] == 8 != 10

세 번째 탐색

indexHigh == 9
indexLow == 8
indexMid == 8

A[8] == 9 != 10

네 번째 탐색

indexHigh == 9
indexLow == 9
indexMid == 9

A[9] == 10 == 10

네 번째 탐색 끝에 찾았다.

선형 탐색은 Index 0 부터 A.length - 1 까지 총 10번의 탐색을 해야 숫자 10을 배열 A 에서 찾을 수 있을 것이다.
이진 탐색은 4번만에 값을 찾아냈다.

구현 코드
https://github.com/MorrisHong/study/blob/main/book-data-structures-the-fun-way/src/main/kotlin/binary_search/BinarySearch.kt

구현 코드를 사용하는 클라이언트 코드
https://github.com/MorrisHong/study/blob/main/book-data-structures-the-fun-way/src/test/kotlin/binary_search/BinarySearchTest.kt