Search⌘ K
Home
Courses
Data Structures and Algorithms in Python

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 exist in the array, we return None to indicate that the number is not present in a list.

Python 3.5
def find(A,target):
  for i in range(len(A)):
    if A[i] == target:
      return i
    return 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 ...