The Binary Search Algorithm in Python

Challenge: How to find a given value in a sorted list?

Example: Say, you have a sorted list:

[1, 4, 10, 42, 99, 102, 103, 999]

Your goal is to find the index of the element 103 in the list. Do you have to check all elements to do this?

Well, only if you used the …

Naive List Search Algorithm

A naive algorithm would compare each element in the list against the searched value.

For example, consider a list of 1024 elements. The naive algorithm performs in the order of 1024 comparisons in the worst-case. ?

(In case you wonder, this is real bad—checking any element in a sorted list to find a specific element is a dumb-ass thing to do!)

In computer science, the worst-case runtime complexity can be expressed via the Big-O notation. We say, for n elements in a list, the naive algorithm needs O(n) comparisons. The O-function defines the asymptotic worst-case growth.

Fortunately, there’s a better and faster way to find an element in a sorted list!

Binary Search Algorithm in Python

The function bsearch is a more effective way to find a value in a sorted list. For n elements in the list, it needs to perform only O(log(n)) comparisons.

Here’s the code:

def bsearch(l, value):
    # search only in index interval (lo:hi)
    lo, hi = 0, len(l)-1
    
    while lo <= hi:
        mid = (lo + hi) // 2
        if l[mid] < value:
            # Mid element is smaller
            # --> skip all left elements
            lo = mid + 1
        elif l[mid] > value:
            # Mid element is larger
            # --> skip all right elements
            hi = mid - 1
        else:
            # We've found the value!
            return mid
    return -1

Exercise: Take a guess—what’s the output of this code snippet when passing the following three function calls?

l = [0, 1, 2, 3, 4, 5, 6]

x = 6
print(bsearch(l,x))

x = 0
print(bsearch(l,x))

x = 3
print(bsearch(l,x))

In case you guessed the following three values, you’ve guessed right!

6
0
3

Applied to a list of 1024 elements, bsearch requires only up to log(1024)=10 comparisons. Hence, bsearch is much faster than the naive comparison algorithm!

In computer science, the worst-case runtime complexity can be expressed via the Big-O notation. We say, for n elements in a list, the naive algorithm needs O(n) comparisons. The O-function defines the asymptotic worst-case growth.

Yes, that’s about 25 comparisons for a list with 42,000,000 elements!!

? <— You

Why is Bsearch so fast?

The naive algorithm compares all elements with the searched value.

Instead, bsearch uses the property that the list is sorted in an ascending manner.

• It checks only the element in the middle position between two indices lo and hi.
• If this middle element is smaller than the searched value, all left-hand elements will be smaller as well because of the sorted list. Hence, we set the lower index lo to the position right of the middle element.
• If this middle element is larger than the searched value, all right-hand elements will be larger as well. Hence, we set the upper index hi to the position left of the middle element.
• Only if the middle element is exactly the same as the searched value, we return the index of this position.

This procedure is repeated until we find the searched value or there are no values left. In each loop iteration, we reduce the search space, i.e., the number of elements between lo and hi, by half.

Interactive Shell Binary Search Python

You can try the bsearch function in the following interactive shell in your browser:

Exercise: Guess the output and run the shell to compare it against the real output!

Code Puzzle Binary Search Algorithm

Another great way to improve your understanding of programming concepts such as the binary search algorithm is to solve code puzzles:

Exercise: Are you a master coder? Test your skills now! Click the puzzle image and try to solve it in our interactive puzzle app!

Related Video Binary Search