First Occurrence in a Sorted Array

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.

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.

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.

#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;
}

#include <iostream>
using namespace std;

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]);
    cout << "First Occurrence Index: " << solve(n, key, arr) << endl;
    return 0;
}

def solve(n, key, arr):
    start = 0
    end = n - 1
    res = -1
    while start <= end:
        mid = start + (end - start) // 2
        if arr[mid] == key:
            res = mid
            end = mid - 1
        elif key < arr[mid]:
            end = mid - 1
        else:
            start = mid + 1
    return res

arr = [5, 10, 10, 10, 20, 20]
key = 10
print("First Occurrence Index:", solve(len(arr), key, arr))

public class FirstOccurrenceFinder {
    public static 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;
    }

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

function solve(n, key, arr) {
    let start = 0, end = n - 1, res = -1;
    while (start <= end) {
        let mid = Math.floor(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;
}

const arr = [5, 10, 10, 10, 20, 20];
const key = 10;
console.log("First Occurrence Index:", solve(arr.length, key, arr));

package main

import "fmt"

func solve(n int, key int, arr []int) int {
    start, end := 0, n-1
    res := -1
    for start <= end {
        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
}

func main() {
    arr := []int{5, 10, 10, 10, 20, 20}
    key := 10
    fmt.Println("First Occurrence Index:", solve(len(arr), key, arr))
}

fn solve(arr: &Vec<i32>, key: i32) -> i32 {
    let mut start = 0;
    let mut end = arr.len() as i32 - 1;
    let mut res = -1;
    while start <= end {
        let mid = start + (end - start) / 2;
        if arr[mid as usize] == key {
            res = mid;
            end = mid - 1;
        } else if key < arr[mid as usize] {
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }
    res
}

fn main() {
    let arr = vec![5, 10, 10, 10, 20, 20];
    let key = 10;
    println!("First Occurrence Index: {}", solve(&arr, key));
}

fun solve(n: Int, key: Int, arr: IntArray): Int {
    var start = 0
    var end = n - 1
    var res = -1
    while (start <= end) {
        val 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
}

fun main() {
    val arr = intArrayOf(5, 10, 10, 10, 20, 20)
    val key = 10
    println("First Occurrence Index: ${solve(arr.size, key, arr)}")
}

func solve(_ n: Int, _ key: Int, _ arr: [Int]) -> Int {
    var start = 0, end = n - 1, res = -1
    while start <= end {
        let 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
}

let arr = [5, 10, 10, 10, 20, 20]
let key = 10
print("First Occurrence Index: \(solve(arr.count, key, arr))")

function solve(n: number, key: number, arr: number[]): number {
  let start = 0, end = n - 1, res = -1;
  while (start <= end) {
    const mid = Math.floor(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;
}

const arr = [5, 10, 10, 10, 20, 20];
const key = 10;
console.log("First Occurrence Index:", solve(arr.length, key, arr));

Time complexity

Space complexity

O(1)

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