Find First Occurrence of an Element in a Sorted Array Using Binary Search

Arrays - Binary Search

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

Given a sorted array of integers and a target number key, your task is to find the first occurrence (leftmost index) of key in the array.

If the element is not found, return -1.

Examples❯

Input Array Key First Occurrence Index Description
[5, 10, 10, 10, 20, 20] 10 1 10 appears at indices 1, 2, 3. First occurrence is at index 1
[2, 4, 4, 4, 6, 6, 8] 4 1 First occurrence of 4 is at index 1
[1, 2, 3, 4, 5] 6 -1 6 does not exist in the array
[1, 1, 1, 1] 1 0 All elements are 1. First index is 0
[1, 2, 3, 4, 5] 3 2 Only one occurrence at index 2

Solution❯

Understanding the Problem

We are given a sorted array and a target number. Our task is to find the first occurrence of that number in the array.

Even though the array is sorted, the same number can appear multiple times. We need the index of the very first one.

For example, consider the array: [1, 2, 2, 2, 3, 4] and the target: 2. The number 2 appears three times, but the first occurrence is at index 1.

Step-by-Step Solution

Step 1: Recognize that the array is sorted

This is a key observation. Because the array is sorted, we can use binary search to quickly narrow down our search space.

Step 2: Modify binary search to continue searching on the left

Normally, binary search stops when it finds the target. But in our case, we need to go further. Once we find the target, we don’t stop—we move to the left side of the array to check if the number appears earlier.

This ensures we always find the first occurrence and not just any one.

Step 3: Edge Case Handling

  • Target not present: If the number does not exist in the array at all, we should return -1.
  • Single-element array: If the array has only one element, we should still handle it correctly.
  • All elements are the target: The algorithm should correctly return index 0.

Why is this efficient?

Instead of checking every element from left to right, we use binary search, which cuts the array in half at each step.

This gives us a time complexity of O(log n), which is much faster than O(n) for large arrays.

Finally

By understanding the nature of the problem (sorted array, repeated elements), and modifying a classic algorithm (binary search), we can solve the problem efficiently and correctly—even with edge cases.

Algorithm Steps❯

  1. Initialize start = 0, end = n - 1, and res = -1 to store the result.
  2. While start ≤ end, calculate mid = start + (end - start) / 2.
  3. If arr[mid] == key: update res = mid and move end = mid - 1 to search left.
  4. If arr[mid] < key: move start = mid + 1.
  5. If arr[mid] > key: move end = mid - 1.
  6. After the loop, res will contain the first occurrence index or -1 if not found.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>

int solve(int n, int key, int arr[]) {
    int start = 0, end = n - 1, res = -1;
    while (start <= end) {
        int mid = start + (end - start) / 2;
        if (arr[mid] == key) {
            res = mid;
            end = mid - 1;
        } else if (key < arr[mid]) {
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }
    return res;
}

int main() {
    int arr[] = {5, 10, 10, 10, 20, 20};
    int key = 10;
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("First Occurrence Index: %d\n", solve(n, key, arr));
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(1)The key is found at the mid index in the first iteration.
Average CaseO(log n)Binary search reduces the search space by half each time.
Worst CaseO(log n)All elements must be checked in the narrowed space to find the first occurrence.

Space Complexity❯

O(1)

Explanation: The algorithm uses only a fixed number of variables regardless of input size.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...