How do you find the first occurrence of a value in a sorted array that has duplicates?
AlgorithmsMid-level
In shortUse a lower-bound binary search for the first index where the element is greater than or equal to the target, then check that the element at that index equals the target. It's O(log n), even with many duplicates.
Model answer
The trick is to not stop when you find the target. Search for the boundary instead: the first index whose element is >= target.
fun firstOccurrence(nums: IntArray, target: Int): Int {
var low = 0
var high = nums.size // half-open: the answer is in [low, high]
while (low < high) {
val mid = low + (high - low) / 2
if (nums[mid] < target) low = mid + 1 else high = mid
}
return if (low < nums.size && nums[low] == target) low else -1
}Why it works: everything before low is smaller than the target, everything from high on is >= the target, and every branch shrinks the range, so the loop ends with low == high at the boundary. Then one check tells you whether the target exists.
The last occurrence is the first index with an element > target, minus one, and the count of the target is the difference between the two boundaries, both in O(log n).
Worth mentioning: Java’s Arrays.binarySearch and Kotlin’s binarySearch return any matching index when there are duplicates, and Swift’s standard library has no binary search, so in an interview you write the lower bound yourself.
What they're looking for
A lower-bound search that keeps narrowing after a match instead of stopping, a clear loop invariant, a range that always shrinks, an overflow-safe midpoint, and awareness that library binary searches return any matching index.
Common mistakes
- Finding any match and then scanning left, which is O(n) for many duplicates.
- low = mid in a low < high loop, which can loop forever.
- Relying on Arrays.binarySearch or Kotlin's binarySearch, which don't guarantee the first index.