Linear Search and Basic Search Logic

A scan is often the right baseline

Linear search needs no preprocessing or sorted input. It is a useful oracle for validating more complex search implementations.

Copy codefun lastIndex(values: IntArray, target: Int): Int {
    for (index in values.lastIndex downTo 0) {
        if (values[index] == target) return index
    }
    return -1
}

Scanning backward directly implements a last-match contract. For an empty array, the progression is empty and the function returns -1. Worst-case time is O(n), auxiliary space O(1).

Binary search is faster per query on sorted data, but sorting solely for one query may cost more overall than scanning. If sorting changes indexes, the result also no longer refers to the original position unless you retain that mapping.

Exercise

Implement first, last, and all-match searches. Test duplicates and compare each return contract. Then analyze the total cost of one query versus a million queries over unchanged data.

Check: choose preprocessing based on workload and required output, rather than selecting binary search merely because its isolated lookup bound is smaller.

Further reading: Searching