Divide and Conquer with Binary Search in Swift

April 21, 2016

A new day, a new algorithm. Today I'd like to go over binary search, or divide and conquer.


Introduction

When you're looking for an item in a sorted array, binary search can drastically reduce the number of steps required. Instead of searching through an array one element at a time, like with Linear Search, you split it into pieces. Here's how that works:

  1. Inspect the element in the middle of the array - is it less than, greater than, or equal to the value we're searching for?
  2. If the middle value is equal to our search value, we're finished!
  3. If the middle value is less than our search value, narrow our search down to the last half of the array (from index m to index n, where m is the index of the middle item, and n is the index of the last item)
  4. If the middle value is greater than our search value, narrow our search down to the first half of the array (from index 0 to index m, where m is the index of the middle item)
  5. Repeat steps 1-4 until either A) the search value is found, or B) the array cannot be split any further, which means the search value was not found in the array.

To help illustrate this, here's an image of the flow:

BinarySearch


Swift Implementation

Here's one way to implement this algorithm recursively in Swift:

 
func binarySearch<T: Comparable>(a: [T], key: T, range: Range<Int>) -> Int? {
    guard range.startIndex < range.endIndex else {
        // If the start index is larger than or equal to the
        // end index, then we've reached the point where the search key
        // could not be found
        return nil
    }
 
    // Find the middle point in the array within the given range
    let midIndex = range.startIndex + (range.endIndex - range.startIndex) / 2
 
    if a[midIndex] > key {
        // Is the search key in the left half?
        return binarySearch(a, key: key, range: range.startIndex ..< midIndex)
    } else if a[midIndex] < key {
        // Is the search key in the right half?
        return binarySearch(a, key: key, range: midIndex + 1 ..< range.endIndex)
    } else {
        // We found our search key - return the index!
        return midIndex
    }
}
 
let list: [Int] = [1, 2, 4, 5, 8, 9, 11, 22, 23, 28, 32, 44]
let indexOfTwentyTwo = binarySearch(list, key: 22, range: 0 ..< list.count)

binary-search.swift on GitHub

And, if you'd like to clean up your call stack a little, here's an implementation without recursion:

func binarySearch<T: Comparable>(a: [T], key: T) -> Int? {
    var range = 0..<a.count
 
    while range.startIndex < range.endIndex {
        // Find the middle point in the array within the given range
        let midIndex = range.startIndex + (range.endIndex - range.startIndex) / 2
 
        if a[midIndex] == key {
            // If we found our search key, return the index
            return midIndex
        } else if a[midIndex] < key {
            // If the mdidle value is less than the key, look at the right half
            range.startIndex = midIndex + 1
        } else {
            // If the midle value is greater than the key, look at the left half
            range.endIndex = midIndex
        }
    }
    return nil
}

binary-search-non-recursive.swift on GitHub


Binary search is an incredibly fast search algorithm at O(log n). Unfortunately, it relies on the array being sorted, so you have to weigh the advantages of a O(log n) search algorithm with the time required to sort your array.

If you already have a sorted array, or if you're sorting an array once and searching multiple times, binary search is probably your best bet.


References

The open source Swift Algorithm Club repository provided much of the explanation here - if you haven't had a chance to check it out, you should!