Implement binary search lower/upper bounds
Company: Amazon
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
##### 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.
Quick Answer: 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.
Binary Search: lower_bound
Given a non-decreasing sorted integer array `nums` of length `n` and a `target` value, implement `lower_bound(nums, target)` iteratively using binary search: return the smallest index `i` such that `nums[i] >= target`. If no such index exists, return `n` (i.e. `len(nums)`), which is the valid insertion point that keeps the array sorted.
Requirements:
- Iterative implementation (no recursion).
- O(log n) time, O(1) extra space.
- Correctly handle: 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.
With duplicates of `target` present, `lower_bound` returns the index of the FIRST occurrence.
Constraints
- 0 <= len(nums) <= 10^5
- nums is sorted in non-decreasing order
- -10^9 <= nums[i], target <= 10^9
- Must be iterative with O(1) extra space
Examples
Input: ([1, 2, 2, 2, 4, 5], 2)
Expected Output: 1
Explanation: First index whose value is >= 2 is index 1 (the first of the three 2s).
Input: ([1, 2, 2, 2, 4, 5], 3)
Expected Output: 4
Explanation: 3 is absent; first value >= 3 is the 4 at index 4 — a valid insertion point.
Hints
- Use a half-open search interval [lo, hi) with lo = 0 and hi = len(nums). Initializing hi to n (not n-1) is what lets the answer legitimately equal n (the not-found / insert-at-end sentinel).
- Loop while lo < hi. When nums[mid] < target, the answer must be strictly right, so set lo = mid + 1; otherwise nums[mid] >= target so mid is a candidate, set hi = mid (do not exclude mid).
- Invariant: every index < lo fails the predicate (nums[i] < target) and every index >= hi satisfies it; the interval shrinks every step, so on exit lo == hi is the first index with nums[i] >= target.
Binary Search: upper_bound
Given a non-decreasing sorted integer array `nums` of length `n` and a `target` value, implement `upper_bound(nums, target)` iteratively using binary search: return the smallest index `i` such that `nums[i] > target` (strictly greater). If no such index exists, return `n` (i.e. `len(nums)`), which is the valid insertion point that keeps the array sorted.
Requirements:
- Iterative implementation (no recursion).
- O(log n) time, O(1) extra space.
- Correctly handle: 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.
With duplicates of `target` present, `upper_bound` returns the index ONE PAST the last occurrence. Note `upper_bound(nums, target) - lower_bound(nums, target)` equals the count of elements equal to `target`. This implementation differs from lower_bound by exactly one comparison: `<=` instead of `<`.
Constraints
- 0 <= len(nums) <= 10^5
- nums is sorted in non-decreasing order
- -10^9 <= nums[i], target <= 10^9
- Must be iterative with O(1) extra space
Examples
Input: ([1, 2, 2, 2, 4, 5], 2)
Expected Output: 4
Explanation: Three 2s at indices 1-3; first value strictly > 2 is the 4 at index 4 (one past the last 2).
Input: ([1, 2, 2, 2, 4, 5], 3)
Expected Output: 4
Explanation: 3 absent; first value > 3 is the 4 at index 4. Same as lower_bound(3) here since 3 is missing.
Hints
- Reuse the lower_bound skeleton with a half-open interval [lo, hi), lo = 0, hi = len(nums). The only change needed is the predicate.
- Partition on the stricter predicate nums[i] > target. Elements equal to target must NOT count, so when nums[mid] <= target push lo = mid + 1; only when nums[mid] > target set hi = mid.
- Because <= sends equal elements to the right, upper_bound lands one index past the last occurrence of target, while lower_bound lands on the first — their difference is the count of target.