When working with sorted arrays, one common problem is to find the first and last occurrence of a given element. This becomes especially interesting when the array contains duplicate values.
In this blog, we’ll walk through an efficient approach using Binary Search and implement it in Java.
🚀 Problem Statement
Given a sorted array arr[] (possibly with duplicates) and a number x, find:
- The first occurrence of
x
- The last occurrence of
x
👉 Example
Input:
arr = [1, 2, 2, 2, 3, 4, 5]
x = 2
Output:
[1, 3]
If x is not present, return:
[-1, -1]
💡 Key Idea
A normal binary search finds any one occurrence of x.
But here, we need the extreme positions:
First occurrence → keep searching on the left side
Last occurrence → keep searching on the right side
So, we modify binary search slightly and run it twice.
⚡ Approach
1. Find First Occurrence
- If
arr[mid] == x, store index and move left
- Continue searching in the left half
2. Find Last Occurrence
- If
arr[mid] == x, store index and move right
- Continue searching in the right half
🧑💻 Java Implementation
import java.util.*;
class Solution {
ArrayList<Integer> find(int[] arr, int x) {
ArrayList<Integer> result = new ArrayList<>();
int first = findFirst(arr, x);
int last = findLast(arr, x);
result.add(first);
result.add(last);
return result;
}
private int findFirst(int[] arr, int x) {
int low = 0, high = arr.length - 1;
int res = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == x) {
res = mid;
high = mid - 1; // move left
} else if (arr[mid] < x) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return res;
}
private int findLast(int[] arr, int x) {
int low = 0, high = arr.length - 1;
int res = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == x) {
res = mid;
low = mid + 1; // move right
} else if (arr[mid] < x) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return res;
}
}
⏱️ Time & Space Complexity
| Aspect | Complexity |
|---|---|
| Time | O(log n) |
| Space | O(1) |
We perform binary search twice, but constants are ignored → still O(log n).
✅ Why This Approach Works
Because the array is sorted, binary search allows us to:
- Eliminate half the search space each time
- Efficiently narrow down the first and last positions
⚠️ Common Mistakes
- ❌ Stopping at the first match (you'll miss duplicates)
- ❌ Not updating the result index before moving left/right
- ❌ Using linear search → O(n), which is inefficient
🎯 Conclusion
This problem is a classic example of how binary search can be adapted beyond simple searching. By slightly modifying the logic, we can solve more advanced problems efficiently.
If you're preparing for coding interviews, mastering such variations is a big win 🚀
SOCIAL SHARE CARD GENERATOR