Beyond equality
The same "remember it, then narrow" idea, aimed at a question that isn't about equality at all. About 10 minutes.
A condition, not a match
"Is this value bigger than x?" is false for the early part of the list and true for a stretch at the end. It is the same kind of yes/no split as before, except there is no "equal" case to look for at all.
Whenever the answer is yes, remember that value as a candidate and keep narrowing to the left, in case a smaller one that still qualifies is hiding there.
answers = []
for x in queries:
low, high, ans = 0, len(nums) - 1, -1
while low <= high:
mid = (low + high) // 2
if nums[mid] > x:
ans = nums[mid]
high = mid - 1
else:
low = mid + 1
answers.append(ans)
return answersThe middle is position 3, value 4. 4 isn't bigger than 4, so it's not a candidate: low = mid + 1.
Works even when x isn't there
The first-occurrence search needed x to actually be in the list, or it handed back minus one. This search doesn't care. It is asking "what is the smallest value past this point?", and that makes sense whether or not x itself shows up.
Like asking for the next train after 9:07 when no train leaves at 9:07.
You want the smallest value greater than 15. The middle is position 2, value 15. What happens next?
[10, 10, 15, 15, 20] · low = 0, high = 4, mid = 2
- ANot a candidate — low = mid + 1
- BRemember 15, then high = mid − 1
- CStop, 15 is the answer
Show the answer
Not a candidate — low = mid + 1. 15 is equal to the target, not greater than it. This search only counts values that are strictly bigger.
The smallest value above a target
nums is sorted from smallest to largest and may have repeats. For each value in queries, return the smallest number in nums that is strictly greater than it, or -1 if none is.
nums = [2, 4, 4, 4, 7, 7, 9], queries = [4, 9, 1] → [7, -1, 2]
0 ≤ n ≤ 2,000,000 · sorted ascending, may repeat · −1,000,000,000 ≤ every value ≤ 1,000,000,000 · up to 2,500 queries