First Occurrence in a Sorted Array

51.4k
0

Given a sorted array of integers that may contain duplicates and a target value, find the index of its first occurrence. If the target value is not present in the array, return -1.

Example 1

Input: arr = [1, 2, 4, 4, 4, 6, 8], target = 4

Output: 2

Explanation: The value 4 appears more than once, and its first appearance is at index 2.

Example 2

Input: arr = [1, 3, 5, 7, 9], target = 6

Output: -1

Explanation: The value 6 is not present in the array, so no first occurrence exists.

Brute Force Approach

The most direct idea is to move from left to right and stop as soon as the target is seen for the first time. That works because the first match found during a left-to-right scan is automatically the first occurrence. If the scan finishes and the target never appears, the answer must be -1.

Algorithm

  • Start from index 0 and check each element one by one because the first match is the one that matters here.

  • Compare the current element with the target at every position.

  • If both values are equal, return that index immediately since no earlier unchecked index is left.

  • If the loop finishes without any match, return -1 because the target is not present in the array.

Dry Run

First Occurrence Brute Dry Run

First Occurrence Brute Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/*
Returns the first index where target appears
in the sorted array.
*/
int firstOccurrence(vector<int>& arr, int target) {
// Check each index from left to right.
for (int i = 0; i < (int)arr.size(); i++) {
// The first matching value is the required first occurrence.
if (arr[i] == target) {
return i;
}
}
return -1;
}
};
// Driver code starts
int main() {
vector<int> arr = {1, 2, 4, 4, 4, 6, 8};
int target = 4;
Solution obj;
cout << obj.firstOccurrence(arr, target) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N), N is the length of array, because in the worst case the whole array may need to be scanned.

Space Complexity: O(1), because only a loop variable is used.

Optimal Approach

The useful observation is this: when arr[mid] is equal to the target, that position is valid, but it may not be the first one. There could still be another same target somewhere on the left side.

So the search should not stop immediately after finding a match. That is the whole trick of this problem. A match is remembered, and then the search continues toward the left to see whether an earlier occurrence exists.

If arr[mid] is smaller than the target, the first occurrence can only be on the right side. If arr[mid] is greater than the target, the answer can only be on the left side.

Algorithm

  • Start with two pointers, low at 0 and high at the last index, because the target can begin anywhere in the array.

  • Keep a variable answer as -1. This stores the best first occurrence found so far, and it stays -1 if the target never appears.

  • Find the middle index using mid = low + (high - low) / 2 so the middle position is calculated safely.

  • If arr[mid] is equal to the target, store mid in answer. Then move high to mid - 1 because an even earlier occurrence may still exist on the left side.

  • If arr[mid] is smaller than the target, move low to mid + 1 because every index up to mid becomes useless for the first occurrence.

  • If arr[mid] is greater than the target, move high to mid - 1 because the target, if present, must lie only in the left half.

  • Continue this process while low <= high.

  • Return answer at the end. If no match was found, it remains -1.

Dry Run

First Occurrence Optimal Dry Run

First Occurrence Optimal Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Function to find the first occurrence using Binary Search
int findFirstOccurrence(vector<int>& nums, int target) {
int n = nums.size();
int low = 0;
int high = n - 1;
int ans = -1;
// Binary search loop
while (low <= high) {
// Compute middle index safely to prevent overflow
int mid = low + (high - low) / 2;
if (nums[mid] == target) {
// Store match index
ans = mid;
// Keep looking left for an earlier occurrence
high = mid - 1;
} else if (nums[mid] < target) {
// Target is on the right side
low = mid + 1;
} else {
// Target is on the left side
high = mid - 1;
}
}
return ans;
}
};
// Driver code starts
int main() {
Solution sol;
vector<int> nums = {1, 3, 5, 5, 5, 5, 67, 123, 125};
int target = 5;
int result = sol.findFirstOccurrence(nums, target);
cout << result << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(log2 N), N is the length of array, because the search range becomes half in each step.

Space Complexity: O(1), because only a few variables are used.

Interview follow-up Questions

Return -1, because there is no valid index where the target appears.

Two PointerMathsBinary SearchArrays

Read Similar Blogs

Arrays

Row wise traversal

Given a matrix with N rows and M columns, print all elements row by row from left to right. Input: mat = [[1, 2, 3], [4, 5, 6]] Output: 1 2 3 4 5 6 Explanation: First row prints as 1 2 3 , then sec...

61.7k
Arrays

Main Diagonal Print

Given a matrix with N rows and M columns, print all elements present on the main diagonal. Input: mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] Output: 1 5 9 Explanation: Main diagonal cells are mat[0][0...

67.1k
Arrays

Search Element in Matrix

Given a matrix with N rows and M columns and a target value X , search for X in the matrix. Return the position of the first occurrence of X as {row, col} . Return {-1, -1} when the target value is...

98.4k
Comments0