Search for a boundary rather than any match
A lower bound is the first index whose value is at least the target. An upper bound is the first index whose value is greater. Both may equal the array length.
fun lowerBound(values: IntArray, target: Int): Int {
var low = 0
var high = values.size
while (low < high) {
val middle = low + (high - low) / 2
if (values[middle] < target) low = middle + 1 else high = middle
}
return low
}
For [1,2,2,4] and target two, the lower bound is one and upper bound is three. Their difference counts occurrences. The invariant is that positions before low are too small, while positions at or beyond high are known candidates or outside the array.
Exercise
Implement upper bound by changing the comparison deliberately. Test empty input, duplicates, missing values, and targets outside the array's range.
Check: verify a returned lower bound before indexing: index < size && values[index] == target. An insertion point is not automatically a match.