Find First and Last Occurrence of Element Using Binary Search in C

When dealing with sorted arrays containing duplicate elements, it is often required to find the first and last positions of a target value.

A simple binary search gives only one occurrence, but we can modify it to find boundaries.

In this tutorial, we will implement an efficient solution using binary search.

Concept Overview

We perform binary search twice:

1. Once to find the first occurrence.

2. Once to find the last occurrence.

This ensures we locate the full range of the target.

Problem Statement

Given a sorted array with possible duplicates, find the first and last index of a target element.

Example

Input:
Array: 1 2 2 2 3 4 5
Target: 2

Output:
First Index: 1
Last Index: 3

Approach

1. Perform binary search to find the first occurrence.

- Move left when match is found.

2. Perform binary search to find the last occurrence.

- Move right when match is found.

3. Return both indices.

C Program

#include <stdio.h>

int findFirst(int arr[], int n, int target) {
    int low = 0, high = n - 1, result = -1;

    while (low <= high) {
        int mid = (low + high) / 2;

        if (arr[mid] == target) {
            result = mid;
            high = mid - 1; // move left
        }
        else if (arr[mid] < target)
            low = mid + 1;
        else
            high = mid - 1;
    }

    return result;
}

int findLast(int arr[], int n, int target) {
    int low = 0, high = n - 1, result = -1;

    while (low <= high) {
        int mid = (low + high) / 2;

        if (arr[mid] == target) {
            result = mid;
            low = mid + 1; // move right
        }
        else if (arr[mid] < target)
            low = mid + 1;
        else
            high = mid - 1;
    }

    return result;
}

int main() {
    int arr[] = {1, 2, 2, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 2;

    int first = findFirst(arr, n, target);
    int last = findLast(arr, n, target);

    printf("First Index: %d\n", first);
    printf("Last Index: %d", last);

    return 0;
}

Output

First Index: 1
Last Index: 3

Detailed Explanation

The first function finds the leftmost occurrence by continuing search on the left side.

The second function finds the rightmost occurrence by continuing search on the right side.

This ensures all duplicate positions are covered.

Time and Space Complexity

Time Complexity: O(log n)

Space Complexity: O(1)

Applications

Used in range queries and frequency counting.

Common in database indexing and search systems.

Advantages

Efficient for sorted arrays.

Handles duplicates effectively.

Limitations

Works only on sorted arrays.

Improvements You Can Make

Return count of occurrences (last - first + 1).

Extend to handle rotated arrays.

Implement recursively.

Mastering boundary-based binary search helps solve many advanced search problems.