Find First and Last Position of a Target
Table of Contents + −
This one looks friendly at first. You get a sorted array. You must find where a number starts and where it ends. But here is the catch. The number can repeat many times. So the interviewer is not testing whether you can find the value. They are testing whether you can find the edges of a block of duplicates without scanning the whole array. That word “sorted” is a big hint. It means binary search is on the table. Your job is to prove you can bend binary search to land on an edge.
🎯 The Problem
You are given a sorted array of integers and a target value. Find the index of the first time the target appears. Find the index of the last time it appears too. If the target is not there at all, return [-1, -1].
Input: nums = [5, 7, 7, 8, 8, 8, 10], target = 8Output: [3, 5]
Input: nums = [5, 7, 7, 8, 8, 8, 10], target = 6Output: [-1, -1]See, the target 8 shows up at index 3, 4, and 5. So the first position is 3 and the last is 5. When the target is missing, we just say [-1, -1].
🐢 The Simple Approach First
The first idea that comes to mind is easy. Walk through the array from left to right. Note the first index where you see the target. Keep updating the last index every time you see it again. At the end you have both.
This works, and it is correct. But think about the size of the array. If it has a million numbers, you touch every single one. That is O(n) time. And the interviewer handed you a sorted array on purpose. A sorted array is a quiet invitation to use binary search. So a plain left-to-right scan throws away the one advantage they gave you. That is why it is not the answer they want.
⚡ The Optimal Approach
Binary search normally stops the moment it finds the target. But with duplicates, the first hit could be anywhere in the block of equal values. So we change the rule.
We run binary search two times.
- The first run looks for the lower bound. The lower bound is the leftmost index where the target sits. When we find the target, we do not stop. We keep moving left to check if an earlier copy exists.
- The second run looks for the upper bound. The upper bound here means the rightmost index where the target sits. When we find the target, we keep moving right instead.
The trick is small. When nums[mid] equals the target, a normal search returns. But for the first position we record mid and then go left. For the last position we record mid and then go right. Each search is still O(log n). Two of them is still O(log n).
Here is how to find the first and last position:
- Run a binary search biased to the left. Every time
nums[mid]equals the target, savemidas a candidate, then search the left half (hi = mid - 1). This lands on the first occurrence. - Run a second binary search biased to the right. Every time
nums[mid]equals the target, savemid, then search the right half (lo = mid + 1). This lands on the last occurrence. - If the first search never found the target, return
[-1, -1]. Otherwise return[first, last].
def find_first(nums, target): # Stop at the leftmost target by going left on every match. lo, hi, ans = 0, len(nums) - 1, -1 while lo <= hi: mid = (lo + hi) // 2 if nums[mid] == target: ans = mid # candidate hi = mid - 1 # keep going left elif nums[mid] < target: lo = mid + 1 else: hi = mid - 1 return ans
def find_last(nums, target): # Stop at the rightmost target by going right on every match. lo, hi, ans = 0, len(nums) - 1, -1 while lo <= hi: mid = (lo + hi) // 2 if nums[mid] == target: ans = mid # candidate lo = mid + 1 # keep going right elif nums[mid] < target: lo = mid + 1 else: hi = mid - 1 return ans
def search_range(nums, target): first = find_first(nums, target) if first == -1: return [-1, -1] return [first, find_last(nums, target)]
nums = [5, 7, 7, 8, 8, 8, 10]print(search_range(nums, 8))The output of the above code will be:
[3, 5]⏱️ Time and Space Complexity
Here is how the two approaches compare. The simple scan is easy to write but slow on big arrays. The two binary searches keep the cost low no matter how many duplicates there are.
| Approach | Time | Space |
|---|---|---|
| Left-to-right scan | O(n) | O(1) |
| Two binary searches | O(log n) | O(1) |
Tip
In an interview, say the words “lower bound” and “upper bound” out loud. Many languages have these built in. C++ has lower_bound and upper_bound. Python has the bisect module with bisect_left and bisect_right. Mention you could use them, but still write the binary search by hand. Interviewers usually want to see that you understand the logic, not just the library call.
🧩 Key Takeaways
- ✅ A sorted array is a hint to reach for binary search, even when you need an edge and not just a match.
- ✅ To find the first position, do not stop on a match. Record it, then keep searching the left half.
- ✅ To find the last position, record the match, then keep searching the right half.
- ✅ Two binary searches together are still O(log n), which beats the O(n) scan on large inputs.
- ✅ The first and last position idea is the same as the lower bound and upper bound idea from library functions.
Check Your Knowledge
Test what you learned. Pick an answer for each question, then click Check.
- 1
Why is a plain left-to-right scan not the preferred answer here?
Why: The scan is correct but O(n); a sorted array invites binary search for O(log n).
- 2
When searching for the FIRST occurrence and nums[mid] equals the target, what should you do?
Why: Recording mid and moving left lets you find any earlier copy of the target.
- 3
What is the total time complexity of running the two biased binary searches?
Why: Each search is O(log n), and two of them is still O(log n).
- 4
Which built-in tools match this first and last position idea?
Why: Lower bound and upper bound functions return exactly these left and right edges.