JavaEasySorting & Searching10 min
Find the first occurrence with binary search
Print the zero-based index of the first target occurrence, or -1 if absent. Follow the stated ordering and edge-case conventions exactly. Interviewers use this task to probe algorithm selection, invariants, and boundary handling.
Input
n, then n sorted integers, then target.
Output
Print the zero-based index of the first target occurrence, or -1 if absent.
Constraints
0 <= n <= 100000; ascending nondecreasing values and target in [-1000000000,1000000000].
Example
Input
5 1 2 2 4 8 2
Output
1
Example 2 input
3 1 2 3 5
Output
-1
This example exercises an absent target above the array range.
Public test cases (2)
Input
5 1 2 2 4 8 2
Expected output
1
Input
3 1 3 5 4
Expected output
-1
Hints (2)
- Identify the state needed to avoid recomputing work for each element.
- Find the lower bound using a half-open search interval, then check equality.
Target complexity: time O(log n) · space O(n) input storage