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

Find the first one

When you find a match, don't stop — keep searching left for an earlier one. About 8 minutes.

Don't stop at the first match

In plain binary search, finding the value is the finish line. With repeats, the middle might land on the third copy of a five, not the first. Picture a row of identical books: you grab one in the middle, but the first one is further left.

So treat a match as a candidate, not the answer, and keep searching the left half in case an earlier copy is hiding there.

Found a match? Remember it, then keep going left.
Too small? Move right as always.
Looking for the first 4target = 4
2
0
4
1
4
2
4
3
4
4
7
5
9
6
lowhigh

The middle is position 3, value 4 — a match! Remember index 3, but keep searching left for an earlier one: high = mid − 1.

Move 1 of 3

The loop still ends the same way

Nothing else changes. Low and high still close in on each other, and the loop still stops once low passes high. The only difference is the answer-so-far variable: every match found while searching left overwrites it, so the last one written is the leftmost, like the furthest-left sticker you've placed on the row of books.

Low not past high: there is still a half that could hold an earlier copy.
No match ever found? The answer stays minus one: x isn't in the list at all.
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
            high = 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 first 5. The middle is position 2, value 5. What happens next?

[3, 5, 5, 5, 5, 8] · low = 0, high = 5, mid = 2
  1. ARemember index 2, then high = mid − 1
  2. BStop right away, index 2 is the answer
  3. CRemember index 2, then low = mid + 1
Show the answer

Remember index 2, then high = mid − 1. It's a match, so it's a candidate — but an earlier copy might still be to the left. Keep searching there.

Your problem

Find the first occurrence

nums is sorted from smallest to largest and may have repeats. For each value in queries, return the first (smallest) 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] → [1, 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.
Sign up free to solve