Katkat
Back

Implement binary search from scratch

UberSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

An Uber software engineer onsite coding question asking you to implement binary search on a sorted integer array from scratch, in both iterative and recursive form. It covers plain search, first/last occurrence with duplicates, the insertion-index variant, overflow-safe midpoint computation, loop invariants and correctness, and time/space complexity analysis.

Question

Implement binary search on a sorted integer array without using any library helpers (no bisect, Arrays.binarySearch, etc.). Provide both iterative and recursive versions, and address each of the following:

  1. Basic search. Return the index of the target if it is present, or -1 if it is absent.
  2. First occurrence. When the array contains duplicates, return the index of the first occurrence of the target.
  3. Last occurrence. When the array contains duplicates, also be able to return the index of the last occurrence of the target.
  4. Insertion index. If the target is absent, return the index at which it could be inserted while keeping the array sorted (the classic "search insert position").
  5. Integer overflow. Compute the midpoint in a way that avoids integer overflow on large indices.
  6. Correctness & invariants. Clearly state your loop invariant and boundary handling (inclusive vs. exclusive bounds), and argue why the search terminates and is correct.
  7. Complexity. State the time and space complexity of each variant.

Example

nums = [1, 2, 2, 2, 5, 7], target = 2
 basic search -> any index in {1, 2, 3}
 first occ. -> 1
 last occ. -> 3

nums = [1, 3, 5, 6], target = 4
 basic search -> -1
 insertion idx -> 2