Data Structures and Algorithms (DSA)  

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

  1. Set low and high

  2. Find mid

  3. If arr[mid] == target:

    • Store mid as answer

    • Move left (high = mid - 1)

  4. If arr[mid] < target, move right

  5. If arr[mid] > target, move left

Step-by-Step Logic for Last Occurrence

  1. Set low and high

  2. Find mid

  3. If arr[mid] == target:

    • Store mid as answer

    • Move right (low = mid + 1)

  4. If arr[mid] < target, move right

  5. If arr[mid] > target, move left

Dry Run Example

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

First Occurrence

lowhighmidaction
063move left
021store & move left
000move right

Answer = 1

Last Occurrence

lowhighmidaction
063store & move right
465move left
444move 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.

Membership not found