First and Last Occurrence of an Element Using Binary Search

Introduction

Finding the first and last occurrence of an element in a sorted array is a very common DSA interview question. Many beginners try to solve it using linear search, which works but is not efficient.

In simple words, this problem asks you to find where a number starts and where it ends in a sorted list.

This article explains the problem in simple, human language, with real-life meaning, and presents a binary search–based solution that interviewers expect.

Real-World Meaning of First and Last Occurrence

Imagine a register book where the same name appears multiple times in a row. If someone asks:

When does this name appear for the first time?
When does it appear for the last time?

You wouldn’t read the entire book line by line. You would quickly narrow down to the correct section. This is exactly what binary search helps us do.

Problem Statement

You are given:

A sorted array of integers
A target value

Your task is to find:

The index of the first occurrence of the target
The index of the last occurrence of the target

Example

Array:  [1, 2, 2, 2, 3, 4, 5]
Target: 2

Output

First Occurrence: 1
Last Occurrence:  3

Before vs After Understanding

Linear Search (Before)

Start from index 0
Check every element
Time-consuming for large arrays

Binary Search (After)

Jump to the middle
Reduce search space by half
Much faster

Why Normal Binary Search Is Not Enough

A normal binary search:

Stops when it finds the element
Does not care if it is the first or last

But in this problem:

We want extreme positions, not just any position

So we slightly modify binary search logic.

What Interviewers Are Actually Testing

Interviewers want to see:

Do you understand binary search deeply?
Can you modify standard logic?
Can you handle duplicate elements?

This problem separates basic learners from strong problem solvers.

Key Idea (Very Simple)

For first occurrence: keep moving left even after finding the target
For last occurrence: keep moving right even after finding the target

We store the answer and continue searching.

Step-by-Step Logic for First Occurrence

Set low and high
Find mid
If arr[mid] == target:
- Store mid as answer
- Move left (high = mid - 1)
If arr[mid] < target, move right
If arr[mid] > target, move left

Step-by-Step Logic for Last Occurrence

Set low and high
Find mid
If arr[mid] == target:
- Store mid as answer
- Move right (low = mid + 1)
If arr[mid] < target, move right
If arr[mid] > target, move left

Dry Run Example

Array: [1, 2, 2, 2, 3, 4, 5], Target = 2

First Occurrence

high	mid	action
6	3	move left
2	1	store & move left
0	0	move right

Answer = 1

Last Occurrence

low	high	mid	action
0	6	3	store & move right
4	6	5	move left
4	4	4	move left

Answer = 3

One-Line Logic Before Code

Modify binary search to continue searching after finding the target.

Code Implementation (C++)

int firstOccurrence(vector<int>& arr, int target) {
    int low = 0, high = arr.size() - 1;
    int ans = -1;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            ans = mid;
            high = mid - 1;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return ans;
}

int lastOccurrence(vector<int>& arr, int target) {
    int low = 0, high = arr.size() - 1;
    int ans = -1;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            ans = mid;
            low = mid + 1;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return ans;
}

Common Beginner Mistakes

Stopping search immediately after finding target
Using normal binary search logic
Forgetting array must be sorted

Bonus: Count Frequency Using Binary Search

Once you have first and last occurrence:

Frequency = lastIndex - firstIndex + 1

This is often asked as a follow-up.

Time and Space Complexity

Time Complexity: O(log n)
Space Complexity: O(1)

This is much faster than linear search.

Easy Summary (Explain Like I’m 10)

If the same number appears many times in a sorted list, binary search helps you quickly find where it starts and where it ends. You just keep looking left for the first position and right for the last position.

Summary

Finding the first and last occurrence of an element using binary search is a powerful extension of the basic binary search algorithm. By slightly modifying the logic and continuing the search even after finding the target, you can efficiently handle duplicate elements. This pattern is very important for interview problems related to frequency counting and boundary searching in sorted arrays.