Member-only story
How To Extend Collections in Swift With Binary Search
Let’s add new features to the foundation types
Many of us have studied algorithms at university or college. Not many of us have actually implemented any of those algorithms.
The standard library (or Foundation for Swift) offers ready-made methods and functions that implement those algorithms. Very few of us have ever implemented a quicksort, but we use methods like invoked the sort daily.
Not all the algorithms we studied are available in the Foundation framework. Today, I’d like to implement one of those algorithms with you, and I want to show you how to add it to every collection in a single shot. Use it in your apps whenever you need it!
Note: Knowing those algorithms and how they work is always useful for any software engineer. Even if we don’t have to implement them, they can offer ideas about how to solve similar problems.
Binary Search
The basic algorithm we are going to implement is the Binary Search.
The binary search works like this: given a sorted collection and an element to find (that we call target), choose the element in the middle. If the middle element is the target, return its index. If the target is less than the middle element, search in the left half of the array. Otherwise, search in the right half.
This algorithm has a strong requirement: the collection must be sorted. This is likely the reason why it has not been implemented in the Foundation library. However, in real life, there are several cases in which we work with sorted data: when searching for a specific date in a historical dataset, when searching for a commit, and when searching for a person in a sorted list.
There are two possible approaches to implement the binary search algorithm: recursive and iterative. I’ll start with the recursive approach because it is more elegant and easier to read.
First of all, let’s start with a skeleton and a global function. Later, we generalize it and move it into the right extension. Here is the code:
