Sorting and Searching

Match searching to ordering

Sorting defines an order; binary search relies on the same order already being present. A binary search result is nonnegative for a match and otherwise encodes the insertion point as -(insertionPoint) - 1.

Copy codefun main() {
    val minutes = listOf(50, 15, 25).sorted()
    check(minutes == listOf(15, 25, 50))
    check(minutes.binarySearch(25) == 1)
    val missing = minutes.binarySearch(30)
    check(missing == -3)
    check(-missing - 1 == 2)
}

For a single search in an unsorted list, sorting first may cost more than a linear scan. Sorting becomes useful when ordered output or repeated searches justify it. For objects, use an explicit comparator and consistent tie-breakers.

Exercise

Sort lessons by difficulty and then title. Search a separately sorted integer list for values before, within, and after its range.

Check: never treat every negative search result as index -1; decode the insertion position if you need to insert while preserving order.

Reference: Ordering