First Occurrence in Sorted Array

Problem

Return the smallest index at which target appears in the sorted list arr, or -1 if it is absent.

Modify binary search so that whenever a match is found you record it and keep searching the left half for an earlier occurrence. This lower-bound search runs in O(log n) time and must handle duplicates.

Hint

On a match, save the index but continue searching left instead of returning immediately.

Test cases

case 1

in: [[1,2,2,2,3],2]

expected: 1

case 2

in: [[1,2,2,2,3],4]

expected: -1

case 3

in: [[],1]

expected: -1

case 4

in: [[5,5,5],5]

expected: 0

case 5

in: [[1,3,5],2]

expected: -1

Starter codePython

def first_occurrence(arr, target):
    # Your code here
    pass

5 test cases · run your code against them in the editor