Sharmila devi

Posted on Mar 24

# Finding First and Last Occurrence in a Sorted Array (Java)

#algorithms #dsa #java #tutorial

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 🚀

Forem