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

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

Visualization Player

Solution❯

To find the first occurrence of a number in a sorted array, we use a modified binary search. Even if we find the target, we keep searching on the left side to check if it appears earlier.

This is more efficient than checking every element and works in O(log n) time due to binary search.

Algorithm Steps❯

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

Code

Java

Python

JavaScript

C++

Kotlin

Swift

Php

public class FirstOccurrenceFinder {
  public static int solve(int n, int key, int[] v) {
    int start = 0;
    int end = n - 1;
    int res = -1;

    while (start <= end) {
      int mid = start + (end - start) / 2;
      if (v[mid] == key) {
        res = mid;       // Record the index
        end = mid - 1;   // Move left to check if it occurs earlier
      } else if (key < v[mid]) {
        end = mid - 1;
      } else {
        start = mid + 1;
      }
    }
    return res;
  }

  public static void main(String[] args) {
    int[] arr = {5, 10, 10, 10, 20, 20};
    int key = 10;
    int result = solve(arr.length, key, arr);
    System.out.println("First Occurrence Index: " + result);
  }
}

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(1)	The key is found at the mid index in the first iteration.
Average Case	O(log n)	Binary search reduces the search space by half each time.
Worst Case	O(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.

⬅ Previous TopicFloor and Ceil in Sorted Array

Next Topic ⮕Last Occurrence in a Sorted Array