Day 22/100 — First and Last Occurrence using Binary Search

Binary Search isn’t limited to finding whether an element exists. One of its most common interview applications is finding the first and last occurrence of an element in a sorted array.

At first glance, it may seem like you need to search linearly after finding the element, but that would increase the complexity to O(n) in the worst case. The beauty of Binary Search is that we can find both occurrences while maintaining O(log n) time complexity.

Let’s understand how.

Problem Statement

Given a sorted array and a target element, return the indices of its first and last occurrence.

Example:

Input:
nums = [1,2,2,2,3,4,5]
target = 2

Output:
[1,3]

If the target doesn’t exist:

Input:
nums = [1,2,3,4]
target = 5

Output:
[-1,-1]

Intuition

A normal Binary Search stops as soon as it finds the target.

But here, finding any occurrence isn’t enough.

We need:

• the leftmost occurrence
• the rightmost occurrence

The idea is simple.

Whenever we find the target:

• Save its index.
• Continue searching instead of stopping.

The direction depends on what we’re looking for.

Finding the First Occurrence

Whenever we find the target,

ans = mid

Instead of returning immediately, continue searching in the left half.

Why?

Because there might be another occurrence before the current one.

So,

high = mid - 1

Eventually, the leftmost occurrence gets stored.

Finding the Last Occurrence

The logic is almost identical.

Whenever we find the target,

ans = mid

But this time we continue searching in the right half.

low = mid + 1

because there could be another occurrence after the current index.

Eventually, the answer becomes the rightmost occurrence.

Algorithm

First Occurrence

1. Perform Binary Search.
2. If target is found: Store index and Move left.
3. If target is greater than mid: Move right
4. Otherwise move left.
5. Return stored answer.

Last Occurrence

1. Perform Binary Search.
2. If target is found: Store index and Move right.
3. If target is greater than mid: Move right.
4. Otherwise move left.
5. Return stored answer.

Dry Run

Array:

[1,2,2,2,3,4,5]

Target = 2

First Occurrence

low = 0
high = 6

mid = 3
nums[mid] = 2

answer = 3
move left

high = 2

Now,

mid = 1

nums[mid] = 2

answer = 1
move left

Again,

high = 0

mid = 0

nums[mid] = 1

move right

Search ends.

First occurrence = 1

Last Occurrence

Again start Binary Search.

mid = 3

nums[mid] = 2

answer = 3
move right

low = 4

mid = 5

nums[mid] = 4

move left

high = 4

mid = 4

nums[mid] = 3

move left

Search ends.

Last occurrence = 3

C++ Solution

class Solution {
public:
    int firstOccurrence(vector<int>& nums, int target) {
        int low = 0, high = nums.size() - 1;
        int ans = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] == target) {
                ans = mid;
                high = mid - 1;
            }
            else if (nums[mid] < target) {
                low = mid + 1;
            }
            else {
                high = mid - 1;
            }
        }
        return ans;
    }
    int lastOccurrence(vector<int>& nums, int target) {
        int low = 0, high = nums.size() - 1;
        int ans = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] == target) {
                ans = mid;
                low = mid + 1;
            }
            else if (nums[mid] < target) {
                low = mid + 1;
            }
            else {
                high = mid - 1;
            }
        }
        return ans;
    }
    vector<int> searchRange(vector<int>& nums, int target) {
        return {firstOccurrence(nums, target),
                lastOccurrence(nums, target)};
    }
};

Complexity Analysis

Time Complexity

• First Binary Search → O(log n)
• Second Binary Search → O(log n)

Overall:

O(log n)

since constants are ignored.

Space Complexity

O(1)

No extra space is used.

Key Takeaways

• Don’t stop Binary Search after finding the target.
• Store the current index and continue searching.
• Move left for the first occurrence.
• Move right for the last occurrence.
• Two Binary Searches still result in O(log n) time complexity.

This pattern is extremely common in coding interviews and serves as the foundation for many Binary Search problems involving boundaries, ranges, lower bounds, and upper bounds. Once you master this variation, you’ll find several other Binary Search questions much easier to solve.

#100DaysOfCode #DSA #BinarySearch #CPP #CodingInterview #LeetCode #ProblemSolving