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

이진 탐색 알고리즘은 배열 내부에서 특정한 값을 찾아내는 알고리즘입니다.

이진 탐색 알고리즘의 과정부터 설명하겠습니다.

1) 배열의 중간에 있는 값을 선택하여 찾고자 하는 값 x와 비교

2) x가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로,

3) x가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색

4) 값을 찾을 때까지 2번 3번 반복

 

즉 , 이진 탐색 알고리즘은 정렬되어있는 배열에서 사용해야합니다.( 크기로 비교하기 때문이죠)

 

예시를 들어볼게요

 

1  2  4  6  9  10  11  19

이러한 배열이 있다고 했을 때, 4라는 값을 찾는 과정입니다.

1) 먼저 이 배열의 중간값은 6입니다. 배열의 끝점의 인덱스가 7이므로 그의 중간은 3.5에서 소수점을 버리기 때문이죠.

2) 4<6이므로 중간값을 기준으로 왼쪽을 탐색합니다.

3) 저희는 이제 1 2 4 만 탐색하면 됩니다.

4) 1 2 4 의 중간값인 2를 탐색하고 4와 비교합니다.

5) 2<4 이므로 중간값을 기준으로 오른쪽을 탐색합니다.

 

이제는 코드로 보겠습니다.

 

fun binarySearch(arr: IntArray, target: Int): Int {
    var low = 0
    var high = arr.lastIndex
    var mid = 0;

    while (low <= high) {
        mid = (low + high) / 2

        when {
            arr[mid] == target -> return mid
            arr[mid] > target -> high = mid - 1
            else -> low = mid + 1
        }
    }
    return -1
}