🔍 How to Find the First Occurrence of an Element in a Sorted Array

Searching for an element in a sorted array is one of the most common problems in Data Structures and Algorithms (DSA). But what if the array contains duplicate elements and you specifically need the first occurrence of a number?

In this article, we’ll explore how to solve this problem efficiently using the Binary Search algorithm.

💡 Problem Statement

Given a sorted array, find the first index where a specific element appears.

If the element is not found, return -1.

Example

Input: arr[] = {1, 2, 2, 2, 3, 4, 5}, key = 2  Output: 1

Explanation: The number 2 appears multiple times, but its first occurrence is at index 1 (0-based indexing).

🧠 Intuition Behind the Problem

A linear search would check each element until it finds the first match — but that takes O(n) time.

Instead, because the array is sorted, we can use a modified binary search that runs in O(log n) time.

The key idea is simple:

• Use binary search to locate the element.

• Even if the element is found, don’t stop there — keep searching toward the left half to check if it appears earlier.

⚙️ Step-by-Step Approach

1. Initialize three variables:

   • low = 0

   • high = n - 1

   • result = -1 (to store the first occurrence index)

2. Perform binary search:

   • Calculate mid = (low + high) / 2

   • If arr[mid] == key, store result = mid, and move left (high = mid - 1)

   • If arr[mid] > key, search in left half (high = mid - 1)

   • If arr[mid] < key, search in right half (low = mid + 1)

3. Continue until low > high.

4. Return result (which holds the first occurrence index or -1 if not found).

💻 C Program Implementation

#include <stdio.h>

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

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

        if (arr[mid] == key) {
            result = mid;       // potential answer
            high = mid - 1;     // move left to find first occurrence
        }
        else if (arr[mid] > key)
            high = mid - 1;
        else
            low = mid + 1;
    }

    return result;
}

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

    int index = firstOccurrence(arr, n, key);

    if (index != -1)
        printf("First occurrence of %d is at index %d\n", key, index);
    else
        printf("Element not found.\n");

    return 0;
}

🧮 Example Dry Run

Input

arr = {1, 2, 2, 2, 3}, key = 2

Step	low	high	mid	arr[mid]	Action	result
1	0	4	2	2	Found → move left	2
2	0	1	0	1	arr[mid] < key → move right	2
3	1	1	1	2	Found → move left	1
4	1	0	—	—	Stop	1

✅ Output → First occurrence = index 1

⏱️ Time & Space Complexity

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

🧩 Key Takeaways

• Use Binary Search instead of Linear Search for sorted arrays.

• Even after finding the key, always search left for earlier occurrences.

• Works efficiently for both large and small datasets.

🎯 Final Thoughts

Finding the first occurrence of an element in a sorted array is a great example of how a small modification in binary search can make your code smarter and faster.

It’s a favorite DSA interview question because it tests your logical thinking and binary search mastery.