Frontend School

Find First Occurrence in Sorted Array

DSA
easy

Find First Occurrence in Sorted Array

Easy
Binary Search
Arrays

Overview

In many data processing systems, efficiently locating specific data points within large, sorted datasets is crucial. Imagine a system that logs sensor readings over time, and these readings are stored in a sorted array. We need a way to quickly find the first instance of a particular reading to analyze its initial impact or to start processing from that point onwards.

What you need to do / Task

Implement a function findFirstOccurrence that takes a sorted array of numbers nums and a target number. Your function should return the index of the first occurrence of target in nums. If the target is not found, return -1.

Input & output

  • nums: A number[] representing a non-decreasingly sorted array of integers.
  • target: A number representing the integer to search for.
  • Returns: A number which is the 0-based index of the first occurrence of target in nums. If target is not present, return -1.

Clarifications

  • The array nums is guaranteed to be sorted in non-decreasing order.
  • nums may contain duplicate values. You must return the index of the first such occurrence.
  • If nums is empty, the target cannot be found, so return -1.

Examples

1

Example 1

Input:

nums = [1, 2, 3, 3, 3, 4, 5], target = 3

Output:

2

Note:

The number 3 appears at indices 2, 3, and 4. The first occurrence is at index 2.

2

Example 2

Input:

nums = [1, 2, 3, 4, 5], target = 6

Output:

-1

Note:

The target 6 is not present in the array.

3

Example 3

Input:

nums = [5, 5, 5, 5], target = 5

Output:

0

Note:

The target 5 appears multiple times. The first occurrence is at index 0.

4

Example 4

Input:

nums = [], target = 7

Output:

-1

Note:

The array is empty, so the target cannot be found.

Constraints

Constraints & assumptions

  • 0 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= target <= 10^9
  • nums is sorted in non-decreasing order.

What interviewers evaluate

  • Correctness: Does the solution accurately find the first occurrence or correctly report absence?
  • Efficiency: Is the solution optimal in terms of time and space complexity (O(log N) time, O(1) space)?
  • Edge Cases: Does the solution handle empty arrays, target not present, target at boundaries, and arrays with all duplicate values?
  • Code Clarity: Is the code well-structured, readable, and easy to understand?

Loading editor...