40% off Premium for a limited time
InterviewLegend

First and Last Occurrence

Alex Chen20 min readEasy
In this lesson
  • Find both first and last occurrence with one boundary template
  • See exactly why classic binary search breaks on duplicates
  • Nail the one-line difference between searching left and searching right

Run plain binary search on [5, 7, 7, 8, 8, 10] looking for 8 and it hands back index 3 or index 4, and you don't get to choose which. That ambiguity is the entire problem. Most people reach for binary search here and then burn half an hour fighting off-by-one bugs, when the fix is a single line off the standard template.

The previous lesson on boundaries did most of this work already. Record the match, then keep searching. Here we run that same move twice: once leaning left for the first occurrence, once leaning right for the last.

Why Classic Binary Search Fails

Vanilla binary search finds some occurrence of the target. It never promises which one:

Array: [5, 7, 7, 8, 8, 10], target = 8

Depending on how the midpoints fall, the search lands on index 3 (the first 8) or index 4 (the last 8). You get no say in it.

The instant classic binary search sees a match it returns, but any old 8 won't do here: we want the two ends of the run of 8s.

The Key Insight

So stop asking "where is the target?" and ask two narrower questions instead:

First occurrence: "Find the leftmost position where nums[i] >= target, then verify it equals target"

Last occurrence: "Find the rightmost position where nums[i] <= target, then verify it equals target"

Both are boundary problems. The first one we already solved last lesson, and the second is its mirror image.

Same template for both, with one difference: which way you keep searching once you hit a match.

Finding the First Occurrence

The first occurrence is exactly the previous lesson. Find a match, record it, then keep searching left, because an earlier one might be sitting there.

Find first 8 in [5,7,7,8,8,10]
5
7
7
8
8
10
0
1
2
3
4
5
L
R
result = -1

Finding the Last Occurrence

The last occurrence is the same logic flipped. On a match, record it and keep searching right instead of left, since a later occurrence might be waiting.

Standing at index 4 on an 8, you can't stop, because index 5 could be an 8 too. So you save where you are, in case it turns out to be the last, and push right.

Find last 8 in [5,7,7,8,8,10]
5
7
7
8
8
10
0
1
2
3
4
5
L
R
result = -1

The Difference is One Line

The gap between first and last is one line of code. Here they are side by side:

python
# Finding FIRST occurrence           # Finding LAST occurrence
if nums[mid] == target:               if nums[mid] == target:
    result = mid                          result = mid
    right = mid - 1  # go LEFT            left = mid + 1   # go RIGHT

That's the whole thing. When you hit a match, the only decision is whether to keep going left (first) or right (last). Nothing else moves.

Try It Yourself

Take a crack at it before opening the solution. Write two helper functions and combine them. The only thing that changes between them is the direction you search after a match.

Try it yourself

First and Last Position

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

Constraints:
• 0 <= nums.length <= 10^5
• -10^9 <= nums[i], target <= 10^9
• nums is a non-decreasing array (may contain duplicates)

Examples

Input: nums = [5,7,7,8,8,10], target = 8

Output: [3, 4]

First 8 at index 3, last 8 at index 4

Input: nums = [5,7,7,8,8,10], target = 6

Output: [-1, -1]

6 does not exist in the array

First and Last Position

Loading...
Click "Run" to execute your code

Test Cases

Input: [5,7,7,8,8,10], 8Expected: [3, 4]
Input: [5,7,7,8,8,10], 6Expected: [-1, -1]
Input: [1], 1Expected: [0, 0]
Input: [], 0Expected: [-1, -1]

Solution

def solution(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# Time: O(log n) | Space: O(1)

Solution

Take some time to think about the problem before revealing the solution. Try to write the code yourself first - that's where the real learning happens.

Things to Watch Out For

Empty array or target missing. Both functions return -1 since result is never updated. No special handling needed.

All elements are the target. find_first returns 0, find_last returns the last index. The "record and continue" pattern handles this naturally.

Skipping the second search. If find_first returns -1, you can skip find_last entirely. That saves a redundant O(log n) pass whenever the target is absent.

Handling Duplicates

People trip on this problem by hacking at vanilla binary search when they should reach for the boundary pattern. On a match, ask whether a better answer could still be out there. For the first occurrence you keep checking left; for the last, you keep checking right, recording each match as you go.

The same move shows up in "find a [[prem:/guides/foundations/binary-search/peak-element|question]]," "search in 2D matrix," and plenty more. The condition changes; recording a candidate and searching on does not.

Key Takeaways

  • Classic binary search finds **any** match, not first or last
  • Use "record and continue" to find boundaries
  • First occurrence: after finding match, search LEFT
  • Last occurrence: after finding match, search RIGHT
  • The entire difference is one line of code
Next: Premium lesson