Find First Entry in List with Duplicates
Explore how to implement a binary search algorithm that locates the first occurrence of a target value in a sorted list containing duplicates. Understand the adjustment needed to standard binary search to handle repeated entries efficiently and reduce search time compared to a linear scan.
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 ...