Katkat
Back

Implement binary search lower/upper bounds

AmazonApplied Scientist · Technical Screen
MediumApplied ScientistTechnical ScreenCoding & Algorithms

Last updated

Implement lower_bound and upper_bound on a non-decreasing sorted array using iterative binary search in O(log n) time and O(1) space. This Amazon ML engineer screen tests precise boundary handling, loop-invariant reasoning, and edge cases like duplicates, empty arrays, and out-of-range targets.

Question

Given a non-decreasing sorted integer array nums of length n and a target value, implement two functions using binary search:

  1. lower_bound(nums, target) — return the smallest index i such that nums[i] >= target. Return n (i.e. len(nums)) if no such index exists.
  2. upper_bound(nums, target) — return the smallest index i such that nums[i] > target. Return n (i.e. len(nums)) if no such index exists.

Requirements:

  • Provide iterative implementations.
  • Achieve O(log n) time and O(1) extra space.
  • Handle the following edge cases: empty array; all elements strictly less than target; all elements strictly greater than target; duplicate values; negative numbers; and targets that fall outside the array’s value range.
  • Include a few test cases that demonstrate correctness.
  • Briefly argue correctness, explaining your boundary conditions and loop invariants.

Note that upper_bound(nums, target) - lower_bound(nums, target) gives the count of elements equal to target, and both functions return a valid insertion point that keeps the array sorted.