Binary Search First Last Occurrence
Fast recall
Quick revision
Core answer
mid and keep searching left (right = mid - 1). For the last occurrence, on a match record mid and keep searching right (left = mid + 1). You store the best index so far and keep narrowing, so both stay O(log n).Whether you can adapt the binary-search template to boundary-finding instead of memorizing one version
Returning immediately on the first match, which gives some occurrence but not the leftmost or rightmost
Note both variants share one template and differ only in the direction you keep searching after a match
Interview-ready guide
Interview answer
The only real difference between finding the first and the last occurrence is which direction you keep searching after you hit the target.
Standard binary search returns the moment it finds a match, but in a sorted array with duplicates that match could be any of the copies, so I change the loop so it doesn't stop early. For the first occurrence, when the middle element equals the target, I save that index in an answer variable and then move right down to mid minus one.
That keeps me searching the left half, because if there's an earlier copy it has to be on the left. I only commit to the answer once the range is exhausted. For the last occurrence it's the mirror image.
On a match I save the index and move left up to mid plus one, which keeps me searching the right half for a later copy. The important thing is that both versions are the exact same template, and they differ in just one line, the direction I move after a match.
That's what I'd want the interviewer to hear, because it shows I understand the pattern rather than memorizing two separate functions.
A common mistake is returning straight away on the first match, which gives you a valid index but not specifically the leftmost or rightmost one. Another is scanning linearly once you find a hit, which collapses to O of n if everything is a duplicate. Done correctly, each search is O of log n, and running both lets me count how many times the value appears as last minus first plus one.
Binary Search First Last Occurrence
Direct Answer
Both reuse the binary-search loop but don't stop on the first match. For the first occurrence, on a match record mid and keep searching left (right = mid - 1). For the last occurrence, on a match record mid and keep searching right (left = mid + 1). You store the best index so far and keep narrowing, so both stay O(log n).
Deep Dive & Architecture
A match is not the end of a boundary search; it is only the best candidate found so far. Save that index, then deliberately discard the half that cannot contain a better boundary.
First occurrence trace
For [1, 2, 2, 2, 5] and target 2, the first midpoint is index 2. Save ans = 2 and continue on indexes 0..1. Index 0 is too small, so move left to 1. Index 1 matches, so save ans = 1 and search farther left. The range is now empty, and 1 is the first position.
Last occurrence trace
Start again at index 2, save it, and continue on 3..4. Index 3 also matches, so save 3 and search 4..4. Value 5 is too large, so the search ends with 3 as the last position.
Both searches halve the remaining range on every step, so each is O(log n). If the first search returns -1, the value is absent; otherwise its count is last - first + 1.
Code Example
int findBound(int[] nums, int target, boolean first) {
int left = 0, right = nums.length - 1, ans = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
ans = mid; // remember this hit
if (first) right = mid - 1; // keep looking left
else left = mid + 1; // keep looking right
} else if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return ans;
}
// nums = {1, 2, 2, 2, 5}, target = 2
// first=true: match at 2 -> ans=2,right=1; match at... ends ans=1 (leftmost)
// first=false: match at 2 -> ans=2,left=3; match at 3 -> ans=3 (rightmost)
// count of 2 = last - first + 1 = 3 - 1 + 1 = 3
Common Mistakes & Pitfalls
- Returning on first match:
if (nums[mid] == target) return mid;gives an arbitrary copy, not the boundary. - Forgetting to store
mid: moving the boundary without savingansloses the match you just found. - Mixing directions: for the first occurrence you move right down (
right = mid - 1); freshers often do the opposite. - Linear scan after a hit: walking left/right from a match degrades to O(n) on
{2,2,...,2}.
Check your understanding
Answer these without looking back at the article.
- How does binary search work and what is its time complexity?
- Why do you use mid = left + (right - left) / 2 instead of (left + right) / 2 in binary search?
- Can binary search be applied to problems other than searching in sorted arrays?
Looking for a structured roadmap?
Every module on this page is also part of the full Java backend interview track.