Free Binary search lessonsBinary search · Stage 1 · First and last position · Step 2

Find the last one

The mirror image of the last step — remember the match, then keep searching right. About 8 minutes.

Mirror the trick

Same idea as the last step, flipped. When you find a match, it might not be the last copy, because a later one could still be further right. It is the same row of identical books, but now you want the rightmost.

Remember the match, then keep searching right instead of stopping.

Found a match? Remember it, then keep going right.

Too big? Move left as always.

Looking for the last 4target = 4

lowhigh

The middle is position 3, value 4 — a match! Remember index 3, but keep searching right for a later one: low = mid + 1.

Move 1 of 3

Watch what a match does to low

Here a match moves low exactly as "too small" does. That is the whole trick: for the last occurrence, both "too small" and "it's a match" push you right. Only "too big" pushes you left. A match is just a "too small" that you also write down as your best answer so far.

Low moves up: when the middle is too small, or equal to x.

High moves down: only when the middle is too big.

In code

answers = []
for x in queries:
    low, high, at = 0, len(nums) - 1, -1
    while low <= high:
        mid = (low + high) // 2
        if nums[mid] == x:
            at = mid
            low = mid + 1
        elif nums[mid] < x:
            low = mid + 1
        else:
            high = mid - 1
    answers.append(at)
return answers

Quick check

You're searching for the last 5. The middle is position 2, value 5. What happens next?

[3, 5, 5, 5, 5, 8] · low = 0, high = 5, mid = 2

ARemember index 2, then low = mid + 1
BRemember index 2, then high = mid − 1
CStop right away, index 2 is the answer

Show the answer

Remember index 2, then low = mid + 1. It's a match, so it's a candidate — but a later copy might still be to the right. Keep searching there.

Your problem

Find the last occurrence

nums is sorted from smallest to largest and may have repeats. For each value in queries, return the last (largest) index where it appears in nums, or -1 if it never appears.

Example

nums = [2, 4, 4, 4, 4, 7, 9], queries = [4, 7, 2] → [4, 5, 0]

0 ≤ n ≤ 2,000,000 · sorted ascending, may repeat · −1,000,000,000 ≤ every value ≤ 1,000,000,000 · up to 2,500 queries

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.