Log inSign up
easyGeeksforGeeksNot Started

First Occurrence of an Element

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Binary Search
Solve on GeeksforGeeks
Lesson

Problem Statement

Given a sorted array of integers arr (which may contain duplicate elements) and a target value target, find the first (leftmost) occurrence index of target.

If target is not present in arr, return -1.

You must write an algorithm with O(log n) runtime complexity.

Example 1 · Multiple Duplicates in Array:

Input: arr = [1, 3, 5, 5, 5, 5, 67, 123, 125], target = 5
Output: 2
Explanation: 5 first appears at index 2.

Example 2 · Target Absent from Array:

Input: arr = [1, 3, 5, 5, 5, 5, 67, 123, 125], target = 10
Output: -1
Explanation: 10 is not in arr so return -1.

Example 3 · Single Element Found at Index 0:

Input: arr = [7, 7, 7, 7], target = 7
Output: 0
Explanation: The first occurrence of 7 is at index 0.

Constraints:

  • 1 <= arr.length <= 105
  • -109 <= arr[i] <= 109
  • arr is sorted in non-decreasing (ascending) order.
  • -109 <= target <= 109

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand why standard binary search is insufficient for duplicate elements.
  • Master the left-continuation branch (high = mid - 1 upon match).
  • Combine first and last occurrence to calculate frequency in O(log N).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Sorted array containing duplicate values
  • Request for the first / leftmost index of target
  • O(log N) runtime constraint

Algorithmic Decision Tree:

  • Initialize low = 0, high = n - 1, ans = -1.
  • If arr[mid] == target: ans = mid, high = mid - 1 (continue left).
  • If arr[mid] < target: low = mid + 1 (search right).
  • If arr[mid] > target: high = mid - 1 (search left).
  • Return ans.

Connected Patterns:

Last Occurrence of an ElementLower BoundFind First and Last PositionCount Occurrences

1. Linear Scan from Left

Intuition

Iterate from index 0 to n - 1. As soon as arr[i] == target, return i immediately since it is the first match encountered.

When to apply: Unsorted arrays or tiny collections.

Algorithm

  1. Step 1: Iterate index i from 0 to arr.length - 1.
  2. Step 2: If arr[i] == target, return index i immediately.
  3. Step 3: If loop completes without match, return -1.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6int firstOccurrence(const vector<int>& arr, int target) {
7 for (int i = 0; i < (int)arr.size(); i++) {
8 if (arr[i] == target) return i;
9 }
10 return -1;
11}
12
13int main() {
14 vector<int> arr = {1, 3, 5, 5, 5, 5, 67, 123, 125};
15 cout << "Linear First Occurrence of 5: " << firstOccurrence(arr, 5) << endl;
16 return 0;
17}

Time & Space Complexity

  • Time complexity: O(N) — Worst case checks all N elements when target is absent or at the end.
  • Space complexity: O(1) — Uses a single loop counter variable.

2. Lower Bound Validation

Intuition

Find lb = lower_bound(arr, target). If lb < arr.length && arr[lb] == target, then lb is guaranteed to be the first occurrence index. Otherwise target is absent, return -1.

When to apply: When a standard lower_bound utility function is already available.

Algorithm

  1. Step 1: Run lower_bound binary search to find smallest index lb where arr[lb] >= target.
  2. Step 2: Check if lb < arr.length and arr[lb] == target.
  3. Step 3: If valid, return lb.
  4. Step 4: Else return -1.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int firstOccurrence(const vector<int>& arr, int target) {
8 auto it = lower_bound(arr.begin(), arr.end(), target);
9 if (it != arr.end() && *it == target) {
10 return distance(arr.begin(), it);
11 }
12 return -1;
13}
14
15int main() {
16 vector<int> arr = {1, 3, 5, 5, 5, 5, 67, 123, 125};
17 cout << "Lower Bound First Occurrence: " << firstOccurrence(arr, 5) << endl;
18 return 0;
19}

Time & Space Complexity

  • Time complexity: O(log N) — Lower bound binary search executes in O(log N) time.
  • Space complexity: O(1) — Constant auxiliary memory.

3. Direct Binary Search with Left Continuation (Gold Standard)

Intuition

Initialize ans = -1, low = 0, high = n - 1. While low <= high: compute mid. If arr[mid] == target, record ans = mid and move left high = mid - 1 to see if an earlier occurrence exists. If arr[mid] < target, move right low = mid + 1. If arr[mid] > target, move left high = mid - 1. Return ans.

When to apply: Industry standard optimal solution for first occurrence in sorted collections.

Algorithm

  1. Step 1: Initialize low = 0, high = arr.length - 1, and ans = -1.
  2. Step 2: Enter while loop with condition low <= high.
  3. Step 3: Calculate mid = low + (high - low) / 2 safely.
  4. Step 4: If arr[mid] == target: update ans = mid and search left (high = mid - 1).
  5. Step 5: Else if arr[mid] < target: search right (low = mid + 1).
  6. Step 6: Else (arr[mid] > target): search left (high = mid - 1).
  7. Step 7: Return ans.

First Occurrence Search Trace

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Initialize low = 0, high = 8, ans = -1
Visual state
Values and pointers at this exact step
array
S
1
3
5
5
5
5
67
123
125
0
↑ low
1
2
3
4
↑ mid
5
6
7
8
↑ high
Variables at this step
low
0
high
8
mid
4
midVal
5
ans
4
Check / comparison
arr[mid] = 5 == target = 5 -> MATCH!
Decision / next transition
Record ans = 4. Search left to find earlier duplicates: high = mid - 1 = 3.
Why this step matters

Initialize low = 0, high = 8, ans = -1. Calculate mid = 0 + (8 - 0) / 2 = 4. arr[4] = 5.

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6int firstOccurrence(const vector<int>& arr, int target) {
7 int low = 0, high = (int)arr.size() - 1;
8 int ans = -1;
9
10 while (low <= high) {
11 int mid = low + (high - low) / 2;
12
13 if (arr[mid] == target) {
14 ans = mid; // Found target, but look for earlier occurrence on left
15 high = mid - 1;
16 } else if (arr[mid] < target) {
17 low = mid + 1;
18 } else {
19 high = mid - 1;
20 }
21 }
22 return ans;
23}
24
25int main() {
26 vector<int> arr = {1, 3, 5, 5, 5, 5, 67, 123, 125};
27 int target = 5;
28 cout << "First Occurrence of " << target << " is at index: " << firstOccurrence(arr, target) << endl;
29 return 0;
30}

Time & Space Complexity

  • Time complexity: O(log N) — Halves search interval each step in log2(N) iterations.
  • Space complexity: O(1) — Uses constant O(1) auxiliary pointer variables.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Linear ScanO(N)O(1)Scan from index 0 until first match.Linear iteration
2.Lower Bound ValidationO(log N)O(1)Find lower bound index and verify equality.None
3.Direct Binary Search Left ContinuationOptimalO(log N)O(1)Direct binary search setting high = mid - 1 on target match.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Returning mid immediately on match (returns arbitrary occurrence instead of first).

Pitfall 2:

Setting high = mid instead of high = mid - 1 on match (causes infinite loop).

Crucial Edge Cases to Validate:

  • Target Not Present: arr = [1, 2, 3], target = 4 -> returns -1.
  • All Elements Identical to Target: arr = [5, 5, 5, 5], target = 5 -> returns index 0.
  • Target Appears Exactly Once: arr = [1, 3, 5, 7], target = 5 -> returns index 2.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Demonstrate how modifying just one line (high = mid - 1 vs low = mid + 1) switches between First Occurrence and Last Occurrence.
  2. Pair this with Last Occurrence to solve 'Count Occurrences in Sorted Array' in 2 * log N time.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why do we execute high = mid - 1 when arr[mid] == target?

2.What does this algorithm return if the target is completely absent from the array?

Back to DSA Sheet