이분탐색 lowerBound & upperBound

'lowerBound'와 'upperBound'는 주로 이분 탐색을 활용해 특정 조건을 만족하는 인덱스를 찾을 때 사용되는 알고리즘입니다. 주로 정렬된 배열이나 리스트에서 사용됩니다

lowerBound

lowerBound는 주어진 배열에서 특정 값 이상이 처음 나오는 위치의 인덱스를 반환합니다.

예시: [1, 2, 3, 4, 5, 5, 6]에서 값 5의 lowerBound는 인덱스 4입니다

upperBound

upperBound는 주어진 배열에서 특정 값보다 큰 값이 처음으로 나오는 위치의 인덱스를 반환합니다.

예시: [1, 2, 3, 4, 5, 5, 6]에서 값 5의 upperBound는 인덱스 6입니다.

---

예시

fun main() {
    val list = listOf(1, 2, 3, 4, 5, 5, 6)

    println(lowerBound(list, 5, 0, list.size))
    println(upperBound(list, 5, 0, list.size))
} // End of main

private fun lowerBound(list: List<Int>, target: Int, low: Int, high: Int): Int {
    if (low == high) return low

    val mid = (low + high) / 2

    return if (list[mid] < target) {
        lowerBound(list, target, mid + 1, high)
    } else {
        lowerBound(list, target, low, mid)
    }
} // End of lowerBound

private fun upperBound(list: List<Int>, target: Int, low: Int, high: Int): Int {
    if (low == high) return low

    val mid = (low + high) / 2
    return if (list[mid] <= target) {
        upperBound(list, target, mid + 1, high)
    } else {
        upperBound(list, target, low, mid)
    }
} // End of upperBound()