Find First Entry in List with Duplicates
In this lesson, you will learn how to find the first entry in a list with duplicates using a binary search in Python.
We'll cover the following...
In this lesson, we will be writing a function that takes an array of sorted integers and a key and returns the index of the first occurrence of that key from the array.
For example, for the array:
[-14, -10, 2, 108, 108, 243, 285, 285, 285, 401]
with
target = 108
the algorithm would return 3, as the first occurrence of 108 in the above array is located at index 3.
The most naive approach to solving this problem is to loop through each element in the array. If you stumble upon the target element, it will be the first occurrence because the array is sorted. Otherwise, if the number does not exist in the array, we return None to indicate that the number is not present in a list.
def find(A,target):for i in range(len(A)):if A[i] == target:return ireturn None
The above code will work, but it will take linear time to complete as the time it takes for the code to execute is proportional to the size of the array for the worst-case.
Let’s go ahead and apply a binary search to make our lives easier to solve this problem. We can reduce the problem from linear Big ...