'lowerBound'와 'upperBound'는 주로 이분 탐색을 활용해 특정 조건을 만족하는 인덱스를 찾을 때 사용되는 알고리즘입니다. 주로 정렬된 배열이나 리스트에서 사용됩니다
lowerBound는 주어진 배열에서 특정 값 이상이 처음 나오는 위치의 인덱스를 반환합니다.
예시: [1, 2, 3, 4, 5, 5, 6]에서 값 5의 lowerBound는 인덱스 4입니다
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()