Find Element in Sorted Array with Duplicates

Prereq: Vanilla Binary Search and Finding the 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.

Input:

  • arr = [2, 3, 5, 7, 11, 13, 17, 19]
  • target = 6

Output: -1

Explanation: 6 does not exists in the array.

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 the Boundary module.

Time Complexity: O(log(n))

Implementation

1from typing import List
2
3def find_first_occurrence(arr: List[int], target: int) -> int:
4    l, r = 0, len(arr) - 1
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
17if __name__ == '__main__':
18    arr = [int(x) for x in input().split()]
19    target = int(input())
20    res = find_first_occurrence(arr, target)
21    print(res)
22