Searching a sorted array for first occurrence

Assume you’re given a sorted list lets try to find the first occurrence of a number.

One solution we could use is to use binary search to find the element and then traverse backwards until we find the first element. This would be fine except in the cases where all the elements are the same as the element we are trying to find. It could lead to O(n) runtime.

An alternative approach is to modify the binary search to keep searching for the number even after finding it. Just a reminder this is what binary search looks like

def bin_search(arr, k):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] < k:
            left = mid + 1
        elif arr[mid] == k:
            return mid
        else:
            right = mid - 1

    return -1

We need to store our found value in a variable since we can find multiple matches and we want to return the earliest one. This way even after finding the element we keep doing binary search until we have broken the while loop. After we have broken the while loop the result will be the earliest version of the element we are trying to find

def bin_search(arr, k):
    left, right = 0, len(arr) - 1
    result = -1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] < k:
            left = mid + 1
        elif arr[mid] == k:
            result = mid
        else:
            right = mid - 1

    return result