Binary Search

In this tutorial, we'll learn about Binary Search, a simple and speedy Search Algorithm.

What is a Binary Search?

A Binary Search is a simple and quick Search Algorithm. It searches for elements within an array, also known as a list, by cutting the list in half and checking if the last element of the half-list is greater than the target element/number. If it is, then we shrink the possible range of the element to that half of the list, and repeat the process until we find the element. Don't worry if you don't understand the concept yet.

Binary Search Implementation

A Binary Search is actually very easy to implement. Below is the implementation of a Binary Search:


def binary_search(arr, target):
    """This function performs a simple Binary Search on arr and searches for target."""
    left = 0
    right = len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif target < arr[mid]:
            right = mid - 1
        else:
            left = mid + 1
    return -1

Running the Code

The code is written in a simple function. It performs a Binary Search on the array, arr, and finds the first occurence of the value of x. If the element is not found, the program returns -1. Otherwise, it returns the index where x is found.

Code Breakdown

The code for a Binary Search is very simple. On the first line, we define a function with

def binary_search(arr, target):

On the next line, we have a multi-line string. When you put a multi-line string on the line right after declaring a function, we call it a doc-string, which tells the developer a little bit about the function. Then, we declare some pointers:


left = 0
right = len(arr) - 1

In our code, we use the pointers to keep track of the range in the list where the target element could be. The whole idea of using Binary Searches is using pointers and then keeping track of the range where our target could be. When the left pointer is greater than the right pointer, it means that the element is not in the list, so our program will return -1.

By using pointers, we are able to determine which range our element is in. Then, we change our pointers according to the if-elif-else statements, so we can shorten our range until we find our target.


mid = (left + right) // 2
if arr[mid] == target:
    return mid
elif target < arr[mid]:
    right = mid - 1
else:
    left = mid + 1

If we do find the target, we'll return the index where we find it. In Python, when we return in a function, the code will automatically break out of the function.

Finally, on the last line, we have return -1. This will just return -1 if the target is not found.