Implement lower_bound and upper_bound binary search
Company: Amazon
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
Implement two functions for a nondecreasing sorted integer array nums of length n: lower_bound(target) returns the smallest index i such that nums[i] >= target, or n if no such index exists; upper_bound(target) returns the smallest index i such that nums[i] > target, or n if no such index exists. Provide iterative implementations with O(log n) time and O(
1) space, handle edge cases (empty array, all elements < or > target, duplicates, negatives), include tests, and briefly argue correctness and boundary invariants.
Quick Answer: This question evaluates proficiency with binary search, precise index and boundary management in sorted arrays, and the ability to reason about algorithmic correctness, loop invariants, and time/space complexity.
