Find Element in Sorted Array with Duplicates
Given a sorted array of integers and a target integer, find the first occurrence of the target and return its index. Return -1 if the target is not in the array.
Input:
arr = [1, 3, 3, 3, 3, 6, 10, 10, 10, 100]
target = 3
Output:
1
Explanation: First occurrence of 3 is at index 1.
Try it yourself
Explanation
The problem is equivalent to finding the boundary of elements < 3 and elements >= 3. Imagine we apply a filter of arr[i] >= 3
, we would get:
Now the problem is reduced to finding the first true
element in a boolean array. And we already know how to do this from Find Boundary module.
Implementation
1 | 1 |
| |
2 | 2 | ||
3 | 3 |
| |
4 | - |
| |
4 | + |
| |
5 | - |
| |
5 | + |
| |
6 | + |
| |
7 | + |
| |
8 | + |
| |
9 | + |
| |
10 | + |
| |
11 | + |
| |
12 | + |
| |
13 | + |
| |
14 | + |
| |
15 | + |
| |
16 | + | ||
6 | 17 |
| |
7 | 18 |
| |
8 | 19 |
| |
9 | 20 |
| |
10 | 21 |
|