Divide and Conquer with Binary Search in Swift

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:

Swift Implementation

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

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

When To Use Binary Search

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!