[알고리즘][KOTLIN] 이진 탐색

정의

• 입력된 배열이 오름 차순 혹은 내림 차순의 배열일 때 선형 탐색보다 빠르게 검색할 수 있는 알고리즘

검색 방법

1. 배열을 오름 차순으로 정열 한다.
2. 배열의 중앙 값을 찾는다.
3. 검색하고자하는 값과 중앙값의 크기를 비교한다.
4. 3번에서 중앙값이 클 경우 중앙 값 기준으로 왼쪽의 배열로 검색 값을 찾는다.
5. 3번에서 중앙값이 작을 경우 중앙 값 기준으로 오른 쪽의 배열로 검색 값을 찾는다.
6. 4, 5 번 과정을 반복한다.

코드

import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    print("요소수 : ")
    val num = sc.nextInt()
    val x = IntArray(num) {
        sc.nextInt()
    }

    x.sorted()
    print("$x")
    print("검색할 값 : ")
    val ky = sc.nextInt()
    val idx = binarySearch(x, num, ky)

    if (idx == -1) {
        println("검색결과가 없어요")
    } else {
        println("검색결과값이 위치 ${idx}에 있어요")
    }
}

private fun binarySearch(x: IntArray, num: Int, key: Int): Int {
    var firstIdx = 0
    var lastIdx = num - 1

    do {
        val midIdx = (firstIdx + lastIdx) / 2

        when {
            x[midIdx] == key -> {
                return midIdx
            }
            x[midIdx] < key -> {
                firstIdx = midIdx + 1
            }
            else -> {
                lastIdx = midIdx - 1
            }
        }
    } while (firstIdx <= lastIdx)

    return -1
}