Progress

0%

Getting Started

Binary Search

Depth First Search/ Backtracking

Breadth First Search

Graph

Two Pointers

Priority Queue / Heap

Divide and Conquer

Dynamic Programming

Other

Data Structure Design

Company Specific

Find Element in Sorted Array with Duplicates

Prereq: 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.

Implementation

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