Find Element in Sorted Array with Duplicates

Prereq: Vanilla Binary Search and Finding Boundary with Binary Search

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.

Time Complexity: O(log(n))

Implementation

1
1
from typing import List
2
2
3
3
def find_first_occurrence(arr: List[int], target: int) -> int:
4
-
    # WRITE YOUR BRILLIANT CODE HERE
4
+
    l, r = 0, len(arr) - 1
5
-
    return 0
5
+
    ans = -1
6
+
    while l <= r:
7
+
        mid = (l + r) // 2
8
+
        if arr[mid] == target:
9
+
            ans = mid
10
+
            r = mid - 1
11
+
        elif arr[mid] < target:
12
+
            l = mid + 1
13
+
        else:
14
+
            r = mid - 1
15
+
    return ans
16
+
6
17
if __name__ == '__main__':
7
18
    arr = [int(x) for x in input().split()]
8
19
    target = int(input())
9
20
    res = find_first_occurrence(arr, target)
10
21
    print(res)