Why it works
- The answer is the first index whose number is not less than the target: the target itself if it is there, the next bigger number if not. If every number is smaller, it is the place after the end, so hi starts at len(nums).
- If nums[mid] < target, the place is after mid: lo = mid + 1. Otherwise mid may be the place itself, so hi = mid keeps it in the range.
- Everything before lo is less than the target, and everything from hi on is not. When lo meets hi, that border is the answer, found or not.
Complexity
Time O(log n): every step halves the range of places. Memory O(1): three indices.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗