Binary search in Kotlin
Find a key in a sorted array. Compare the key with the middle item, and keep only the half that can hold the key.
- File
BinarySearch.kt, 20 lines- Level
- Native tests
- pass in this build
- Toolchain
- Kotlin 2.3 on JDK 25
- Test framework
- JUnit 5
- Run the tests
kotlinc and the JUnit console launcher
// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/binary-search/. The authors are listed in prov/2B7QDX.jsonl.
/** Returns an index i with a[i] == x, or -1 when x is not in a. The list must be sorted. */
fun <T : Comparable<T>> binarySearch(a: List<T>, x: T): Int {
var lo = 0 // @line L1
var hi = a.size
while (lo < hi) { // @line L2
val mid = lo + (hi - lo) / 2 // @line L3
val c = a[mid].compareTo(x)
if (c < 0) { // @line L4
lo = mid + 1 // @line L5
} else if (c > 0) { // @line L6
hi = mid // @line L7
} else {
return mid // @line L8
}
}
return -1 // @line L9
}
BinarySearchTest.kt 37 lines
// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/binary-search/. The authors are listed in prov/2B7QDX.jsonl.
import kotlin.random.Random
import org.junit.jupiter.api.Assertions.assertEquals
import org.junit.jupiter.api.Test
class BinarySearchTest {
@Test
fun examples() {
val a = listOf(2, 5, 8, 12, 16, 23, 38, 56, 72, 91)
assertEquals(5, binarySearch(a, 23))
assertEquals(0, binarySearch(a, 2))
assertEquals(9, binarySearch(a, 91))
assertEquals(-1, binarySearch(a, 30))
assertEquals(-1, binarySearch(a, 1))
assertEquals(-1, binarySearch(a, 100))
}
@Test
fun edges() {
assertEquals(-1, binarySearch(emptyList<Int>(), 1))
assertEquals(0, binarySearch(listOf(7), 7))
assertEquals(1, binarySearch(listOf("ant", "bee", "cat"), "bee"))
}
@Test
fun randomAgainstLinearScan() {
val rng = Random(2150)
repeat(2000) {
val a = List(rng.nextInt(31)) { rng.nextInt(41) - 20 }.sorted()
val x = rng.nextInt(51) - 25
val got = binarySearch(a, x)
if (x in a) assertEquals(x, a[got]) else assertEquals(-1, got)
}
}
}
What the next level needs
- I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work