Skip to content

Instantly share code, notes, and snippets.

@geoand
Created April 1, 2016 10:13
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save geoand/acd6389ea27fccb40842ef35ad587002 to your computer and use it in GitHub Desktop.
Save geoand/acd6389ea27fccb40842ef35ad587002 to your computer and use it in GitHub Desktop.
tailrec fun <T : Comparable<T>> binarySearch(list: List<T>, item: T, startIndex: Int = 0, endIndex: Int = list.size - 1): Int {
if (endIndex < startIndex ) {
return -1
} else if (startIndex == endIndex) {
return if (item == list[startIndex]) startIndex else -1
} else if (endIndex == startIndex + 1) {
if (list[startIndex] == item) {
return startIndex
}
else if(list[endIndex] == item) {
return endIndex
}
return -1
} else {
val midIndex = (endIndex - startIndex) / 2 + startIndex
val midValue = list[midIndex]
val (newStartIndex, newEndIndex) = if (item < midValue) Pair(startIndex, midIndex) else Pair(midIndex, endIndex)
return binarySearch(list, item, newStartIndex, newEndIndex)
}
}
val list = arrayListOf(1, 2, 3, 4, 5, 10)
fun main(args: Array<String>) {
assert(binarySearch(list, 1) == 0)
assert(binarySearch(list, 2) == 1)
assert(binarySearch(list, 5) == 4)
assert(binarySearch(list, 10) == 5)
assert(binarySearch(list, 11) == -1)
assert(binarySearch(list, 6) == -1)
}
fun assert(value: Boolean) {
if (!value) {
throw AssertionError("Value was false")
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment