Implementation of Binary Search in Python

In this post, we'll look at how a binary search is executed using Python.

What is a binary search?

In computer science, a binary search (also called a half-interval search) algorithm finds the position of a target value within a sorted array.

Here's how it works, in general: Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty. 

Requirements

To apply the Binary Search algorithm to a sequence, the sequence already has to be sorted in ascending order. Otherwise, the algorithm will not find the correct answer. If it does, it will be by pure coincidence.

Input and Output

The algorithm (implemented as a function) needs this data:

• An ordered sequence of elements (for example: list, tuple, string).
• The target element that we are searching for.

It returns the index of the element that you are looking for if it's found. If the element is not found, -1 is returned.

Efficiency

It is very efficient compared to Linear Search (searching for an element one by one, starting from the first one) because we are able to "discard" half of the list on every step.

Binary Search in Python

Below is the Python code for conducting a binary search:

Let's break it down line by line.

Header

Here we have the function header. It takes two arguments:

• "data" is the ordered sequence of elements (for example: list, tuple, or string).
• "elem" is the element that we want to find.

Initial Interval

The next line sets the initial lower and upper bounds. The initial lower bound is index 0 and the initial upper bound is the last index of the sequence.

Loop

We will repeat the process while there is a valid interval, while the lower bound is smaller than or equal to the upper bound.

Middle Element

On every iteration, we need to find the index of the middle element. To do this, we add the lower and upper bounds and divide the result by 2 using integer division.

Comparisons

With these conditionals (see below), we determine what to do depending on the value of the middle element data[middle]. We compare it to the target element that we are looking for. There are three options:

• If the middle element is equal to the element that we are looking for, we return the index immediately because we found the element.

• If the middle element is greater than the element that we are looking for, we reassign the upper bound because we know that the target element is in the lower half of the list.

• Else, the only option left is that the middle element is smaller than the element that we are looking for, so we reassign the lower bound because we know that the target element is in the upper half of the list.

Element Not Found

If the loop is completed without finding the element, the value -1 is returned.