20180714
https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.collections/binary-search.html
kotlin에서도 Java 처럼 binarySearch를 해주는 함수가 있다.
fun <T> Array<out T>.binarySearch(
element: T,
comparator: Comparator<in T>,
fromIndex: Int = 0,
toIndex: Int = size
): Int
대상 Array는 comparator를 기준으로 정렬되어있다고 전제하고 수행한다.
정렬이 되어있지 않으면 undefined한 결과가 나온다.
element가 Array의 주어진 범위 안에 존재하면 해당 element의 index를 리턴해준다.
fromIndex, toIndex로 범위를 지정해도 전체 범위에서의 index를 리턴해준다.
주의할 점은, element가 여러 개 중복해서 들어있다면 어떤 것이 출력될 지 알 수 없다.
element가 Array의 주어진 범위에 없다면 - (해당 element가 들어가야하는 위치) - 1 을 리턴해준다.
이 때, 들어가야하는 위치는 element가 Array에 들어가도 정렬된 상태가 유지되는 위치를 말한다. 즉, 현재 Array 에서 element 보다 큰 최소 원소의 위치.
-1 을 해주는 이유는
arr = intArrayOf(1,2,4,7,9)
println(arr.binarySearch(0)) // -1
element가 가장 앞에 들어가야 할 때, 그냥 0을 출력해버리면 찾은 것인지 아닌지 알 수 없기 때문이다.
고민할 것 없이 음수일때 .inv() 로 보수처리를 해버리면 된다.