PythonEasySorting & Searching10 min
Find the first occurrence with binary search
Indices are zero-based. The array is sorted in nondecreasing order and may contain duplicates. Interviewers use this problem to assess search for the first position whose value is at least the target.
Input
First line: n and target. Second line: n sorted integers.
Output
Print the result on one line; print an empty line for an empty string.
Constraints
0 <= n <= 100000; values and target are between -10^9 and 10^9.
Example
Input
6 2 1 2 2 2 5 9
Output
1
Example 2 input
3 10 -10 0 10
Output
2
The final index is a valid match.
Public test cases (2)
Input
6 2 1 2 2 2 5 9
Expected output
1
Input
3 4 1 3 5
Expected output
-1
Hints (2)
- Identify the state needed to avoid repeated work.
- Search for the first position whose value is at least the target.
Target complexity: time O(log n) · space O(1)