Tag: binary search

Studying data structures and algorithms is often a frustrating experience for those looking to get into a software engineering role. However, learning the ins and outs of these algorithms can make you a better programmer. Understanding how basic algorithms like binary search and selection sort operate can aid you in thinking in terms of algorithms, giving you a better intuition for how to break complex problems down into simple, solvable steps. 

In this blog series, I plan on doing a dive into many of the data structures and algorithms programmers need to know. There’s a wide variety of data structures/algorithms to learn about, but we all have to start somewhere. I’ll be starting with a breakdown of a common searching algorithm: binary search.

Understanding Binary Search

Binary search, sometimes called logarithmic search (in reference to its average run-time), is a searching algorithm designed to find items within an array. Binary search assumes that the array in question is sorted.  The “binary” in binary search comes from the fact that it operates by diving an array up into two parts and then recurring this division until the specified value is found or until the no more splits are possible (meaning the item is not found in the array).

The steps of implementing binary search can be broken down as follows:

1. Start by selecting the middle value in the array.
2. When given some target value – X, compare X with the middle element of the array.
3. If target value X matches the middle value, return it.
4. If the middle vale and X aren’t equal, we check the target value against the middle value. If X is a greater value than the middle element, it follows that X can only be found in the right half of the array, which means that we recur on the right half.
5. If X is smaller than the middle value, we carry out the actions in step 4, but for the left half of the array instead.

If the number of elements in the array is even instead of odd, this means there isn’t a middle value. So instead, we select the left value plus the right value minus one, and divide everything by 2. Doing this ensures that there is always a value that can be selected as the middle value.

Implementation of Binary Search In Python

There are two ways to implement a binary search algorithm in Python: a recursive implementation and an iterative implementation.

Iterative implementations are actually preferred in Python, as Python has a maximum recursion depth, a point at which Python will cease recurring as a guard against stack overflows.

Let’s cover the recursive implementation first.

To start off with, we’ll create a function that takes in an array, a left value, a right value, and a target X value. 

First, we’ll check the right half of the array, selecting the middle value. If the middle value happens to be the target value, we can just return it and end there.

Otherwise, we need to compare the value and find out if it is bigger or smaller than he middle value. If it’s bigger, it can only be in the right half, and if smaller it can only be in the left half. We can make another call and carry out the same function recursively.

Finally, if the we’ve run through the whole array and none of the values matched our target, we conclude that the value isn’t in the array and end the search.

def binary_search(arr, left, right, target):

    not_found = "null"

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

Now let’s run the code and check the output.

arr = [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

def run_binary_search(arr, target):
    result = binary_search(arr, 0, len(arr) - 1, target)

    if result == "null":
        print("Target not in array.")
    else:
        print("Target is in array - position: {}".format(result))

run_binary_search(arr, 2)
run_binary_search(arr, 12)
run_binary_search(arr, 19)
run_binary_search(arr, 25)

Output is:

Target is in array – position: 0
Target is in array – position: 10
Target not in array.
Target not in array.

I mentioned earlier that  Python actually prefers an iterative approach to searching, avoiding recursion where possible. Let’s go over the iterative approach for Binary search in Python now.

It’s more or less just the same as the recursive approach, except that instead of calling the function recursively we use a “while” loop, so that as long as the array has values which haven’t been searched, it carries out the binary searching process.

def binary_search_iterative(arr, left, right, target):

    not_found = "null"

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

arr = [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

def run_binary_search_iterative(arr, target):
    result = binary_search_iterative(arr, 0, len(arr) - 1, target)

    if result == "null":
        print("Target not in array.")
    else:
        print("Target is in array - position: {}".format(result))

run_binary_search_iterative(arr, 25)
run_binary_search_iterative(arr, 3)

Output is:

Target not in array.
Target is in array – position: 1