Binary Search Implementations

In the previous videos we introduced two versions of binary search, an iterative and a recursive version. Code snippets for the iterative versions are provided below and match the explanation provided in the videos.

You will find the recursive version to be slightly different however. If you remember, when starting the recursive version of binary search I made one modification to the algorithm - instead of returning the index value, I returned True if the value was present in the list and False otherwise. There was a reason for that.

When we use list slices with recursive calls the index value returned, even with a successful search will always be 0. Each sublist created will have a new set of indexes and it becomes very difficult to track the relationship betwee the index of an item in the sublist and where that item existed in the original list.

In the worst case scenario, where it takes a log n + 1 number of splits to find the element we end up with a single element array. The target, at this point, will always be at index position 0 regardless of its index position in the original array.

While we were able to demonstrate how recursion worked and provide a recursive implementation of binary search, this is not a good implementation. For all the code snippets below I have provided the correct implementation for the recursive version of binary search.

It's not that much different and it might even seem familiar to you - it combines the techniques we used in both the iterative version and recursive version of binary search.

For an explanation of this version and some of its implications, read the Python section below. You should then be able to look for code snippets in the language of your choice understand what the code is doing.

Python

Iterative Binary Search

def binary_search(list, target):
    first = 0
    last = len(list) - 1

    while first <= last:
        midpoint = (first + last)//2
        if list[midpoint] == target:
            return midpoint
        elif list[midpoint] < target:
            first = midpoint+1
        else:
            last = midpoint-1
    return -1

Recursive Binary Search

The way we've tackled the recursive version of binary serach is by using a combination of a recursive call and the iterative approach with start and end variables to keep track of the portion of the list we're searching.

def recursive_binary_search(list, target, start=0, end=None):
    if end is None:
        end = len(list) - 1
    if start > end:
        return -1

    mid = (start + end) // 2

    if target == list[mid]:
        return mid
    else:
        if target < list[mid]:
            return recursive_binary_search(list, target, start, mid-1)
        else:
            return recursive_binary_search(list, target, mid+1, end)

The function has been modified to accept a start and end position with default values of 0 and None respectively. The default values allow us to pass a list and target without needing to specify the arguments when invoking the function. Inside the body we set the appropriate values like we did when setting first and last in the iterative approach.

We then use start and end like we did in the iterative approach to keep track of the slice of the list we're searching through. The big difference here is that with each recursive call, by passing in different values for start and end we can define the slice of the list we're searching through. We're not actually executing a slice operation and we use only one list in memory, but each recursive call now focuses on a smaller slice of the original list.

This definitely has implications for the runtime of our code. One point that was not covered in the course was the cost of the slice operation used in the recursive version of the function. A slicing operation is not a constant time operation and has a runtime of O(k) where k represents the size of the slice.

With the modified (and correct) version of recursive binary search, since we're not executing slicing operations we've eliminated that cost and our code now reflects the accurate runtime of the binary search algorithm at O(log n).

Slicing is also what lends to a space complexity of O(log n) for the original recursive version since each slice required additional storage. Since we're not slicing the lsit anymore, the space complexity is now constant - no additional storage is used.

It's important to keep in mind that this doesn't change the fact that Python has a maximum recursion depth and an iterative approach is still preferred.

JavaScript

function binarySearch(array, key) {
    let left = 0;
    let right = array.length - 1;
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        if (array[mid] === key) {
            return mid;
        }
        if (array[mid] < key) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

Swift

In Swift we can opt to use either the iterative or recursive implementation since Swift implements tail call optimization and maximum recursion depth is not an issue.

Iterative Binary Search

func binarySearch(_ a: [Int], key: Int) -> Int? {
    var upperBound = 0
    var lowerBound = a.index(before: a.endIndex)

    while upperBound <= lowerBound {
        let mid = (upperBound + lowerBound)/2

        if a[mid] == key {
            return mid
        } else if a[mid] < key {
            upperBound = mid + 1
        } else {
            lowerBound = mid - 1
        }
    }

    return nil
}

Recursive Binary Search

func recursiveBinarySearch<T: Comparable>(_ a: [T], key: T, lower: Int, upper: Int) -> Int? {
    if lower > upper {
        return nil
    } else {
        let mid = (lower + upper)/2

        if a[mid] == key {
            return mid
        } else {
            if a[mid] < key {
                return recursiveBinarySearch(a, key: key, lower: mid + 1, upper: upper)
            } else {
                return recursiveBinarySearch(a, key: key, lower: lower, upper: mid - 1)
            }
        }
    }
}

Java

Iterative Binary Search

public class IterativeBinarySearch {
    public static Integer binarySearch(int[] input, int target) {
        int first = 0;
        int last = input.length - 1;

        while (first <= last) {
            int mid = (first + last) / 2;

            if (input[mid] == target) {
                return mid;
            } else if (input[mid] < target) {
                first = mid + 1;
            } else {
                last = mid - 1;
            }
        }

        return null;
    }
}

Recursive Binary Search

public class RecursiveBinarySearch {
    public static int binarySearch(int[] input, int target, int start, int end) {
        if (start >= end) {
            return -1;
        } else {
            int mid = start + (end - start) / 2;

            if (target < input[mid]) {
                return binarySearch(input, target, start, mid-1);
            } else if (target > input[mid]) {
                return binarySearch(input, target, mid+1, end);
            } else {
                return mid;
            }
        }
    }
}

PHP

Iterative Binary Search

<?php
function iterative_binary_search($list, $target) 
{
    $first = 0;
    $last = count($list)-1;

    while ($first <= $last) {
        $mid = ($first + $last) >> 1;

        if ($list[$mid] == $target) {
            return $mid;
        } elseif ($list[$mid] > $target) {
            $last = $mid - 1;
        } elseif ($list[$mid] < $target) {
            $first = $mid + 1;
        }
    }

    return -1;
}   
?>

Recursive Binary Search

<?php
function binary_search($list, $target, $start, $end) 
{
    if ($start > $end)
        return -1;

    $mid = ($start + $end) >> 1;

    if ($list[$mid] == $target) {
        return $mid;
    } elseif ($list[$mid] > $target) {
        return binary_search($list, $target, $start, $mid-1);
    } elseif ($list[$mid] < $target) {
        return binary_search($list, $target, $mid+1, $end);
    }
}
?>