First Last Occurrence Binary Search | Java Fresher Interview
Fast recall
Quick revision
Core answer
right = mid - 1). For the last position, record and keep searching right (left = mid + 1). Each is O(log n), far better than finding one match and scanning, which is O(n) when the array is all duplicates.Whether you can turn the standard template into a leftmost/rightmost search and keep it logarithmic
Finding any match then linearly scanning outward, degrading to O(n) on heavy duplicates
Use a stored result variable and explain count = last - first + 1 in O(log n)
Interview-ready guide
Interview answer
To find the first and last position of a value in a sorted array I run two binary searches, and the key change in both is that I don't stop when I find a match.
For the first position, I do a normal binary search, but when the middle element equals the target I save that index in a result variable and then move right down to mid minus one. That keeps me searching the left half, because any earlier copy of the target has to be on the left. I keep going until the range is empty, and the saved index is the leftmost occurrence.
For the last position it's the mirror image: on a match I save the index and move left up to mid plus one, so I keep searching the right half for a later copy. Both searches stay O of log n because I'm still halving the range each step, I've just changed what I do on a match.
The mistake I want to avoid is finding one match with binary search and then walking outward with a loop to find the edges. That looks fine, but if the array is all the same value, that linear walk is O of n and defeats the purpose. Using the stored result variable keeps everything logarithmic.
A nice bonus is that once I have the first and last indices, the number of times the value appears is just last minus first plus one, computed in constant time. This is exactly LeetCode thirty-four, and it's a clean example of adapting the standard template to find boundaries instead of any single match.
First Last Occurrence Binary Search | Java Fresher Interview
Direct Answer
Run two boundary binary searches that don't stop on the first match. For the first position, on a match record the index and keep searching left (right = mid - 1). For the last position, record and keep searching right (left = mid + 1). Each is O(log n), far better than finding one match and scanning, which is O(n) when the array is all duplicates.
Deep Dive & Architecture
A normal binary search may return any matching duplicate. To find a range, run two searches. Both save a matching index, but the first search continues left and the last search continues right.
Worked example: [1, 2, 2, 2, 5], target 2
For the first occurrence, midpoint 2 matches, so save 2 and search indexes 0..1. Index 1 also matches, so save 1 and search farther left. The range closes with first index 1.
For the last occurrence, start again. Midpoint 2 matches, so save 2 and search 3..4. Index 3 matches, so save 3 and search right once more. Value 5 is too large, and the final last index is 3. The result is [1, 3], and the count is 3 - 1 + 1 = 3.
Do not stop at the first match; that loses the boundary information. Also handle the absent case explicitly: if the first search returns -1, return [-1, -1] without calculating a count.
Each search halves the remaining range, so total time is still O(log n), and the iterative form uses O(1) extra space.
Code Example
int[] searchRange(int[] nums, int target) {
return new int[]{ bound(nums, target, true), bound(nums, target, false) };
}
int bound(int[] nums, int target, boolean first) {
int lo = 0, hi = nums.length - 1, ans = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target) {
ans = mid;
if (first) hi = mid - 1; else lo = mid + 1; // keep narrowing
} else if (nums[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return ans;
}
// nums = {1,2,2,2,3,4,5}, target = 2
// first -> 1, last -> 3, count = 3 - 1 + 1 = 3
Common Mistakes & Pitfalls
- Linear scan after a hit: O(n) on
{2,2,...,2}- the whole point is to avoid that. - Returning on first match: yields an arbitrary copy, not the boundary.
- Not storing
ans: moving boundaries without saving the index loses the match. - Off-by-one on count: it's
last - first + 1, notlast - first.
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.