Home » App Development » Play With Code: Binary Search in Swift

Play With Code: Binary Search in Swift

Written by LearnAppMaking on March 26 2021 in App Development, Play With Code, Swift

Binary search is a simple algorithm that lets you search an array for a specific value. It’s trivial to implement in Swift, which makes it exceptionally helpful for beginners as an introduction into algorithms. And it’s also a lot of fun!

In this tutorial, we’re going to code a binary search algorithm from scratch in Swift. It’s good practice, and we’ll learn some interesting tidbits about Swift along the way.

Ready? Let’s go.

Finding a Value in an Array of Integers

Imagine you’ve got an array of numbers, like this one:

let numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

You need to find a number in this array of integers. For example, the number 13. But why would you try to find it? It’s right there, between 11 and 17!

Well, consider that you need to know the array index of number 13, because you need to update or delete that number from the array. The only way to do that is by using its index.

numbers.remove(at: ···) // What's the index of number 13?

How do we find the index for number 13? The naive approach is to loop over every number in the array to check if it’s 13. Like this:

for (index, number) in numbers.enumerated() {
    if number == 13 {
        print("Found it! It's index \(index)")
    }
}

This works, but it’s also inefficient. In the worst-case scenario, you need to iterate over every number in the array to find the one you’re looking for.

Technically speaking, we’re saying that the time complexity of the above algorithm is O(n) – and that’s not good enough! Can we do better?

Keep in mind that binary search only works for sorted arrays, and for numbers that can be compared logically. Binary search is related to the binary tree data structure, in which values can be looked up incredibly fast.

How Binary Search Works

A better approach is the binary search algorithm. In short, binary search works by constantly dividing the array of numbers in half, until we’ve found the number we’re looking for. Because the array is sorted, we can use logic to figure out in which half of the array the number is.

Let’s first discuss how the algorithm works exactly, before we write it in code. Here, check out this diagram:

How does it work? Let’s go over it, step by step. First, we’re starting out with an array of integers. They’re sorted smallest to biggest.

2, 3, 5, 7, 11, 13, 17, 19, 23, 29

Each item in the array has an index number. These indices start at 0, and stop at the end of the array. The last index number in the array is equal to the size of the array minus one. Like this:

Index: 0,  1,  2,  3,  4,  5,  6,  7,  8,  9
Value: 2,  3,  5,  7, 11, 13, 17, 19, 23, 29

We’re looking for the index for number 13 in the array. You can easily see that the right answer is index 5, but how can we get there with code without iterating over each number?

Here’s how:

Find the middle item in the array: value 11 at index 4. We can calculate the middle item by taking the last index, dividing it by 2, and rounding that down (“floor”).
Compare the middle item to the number we’re looking for. 11 is smaller than 13, so we’re continuing with the right half of the array (and forget the left half).
Again, we’re finding the middle item of the remaining half: value 19 at index 7. (You’ll see in the code, later on, how we’re calculating that middle index.)
Compare the middle item to the number we’re looking for. 19 is bigger than 13, so now we’re continuing with the left half of the remaining array (and forget the right half).
We’re now left with two numbers: 13 and 17. We’re taking the middle item, and rounded down, that’s 13 at index 5. We’re now comparing that middle number 13 against the number 13 we’re looking for, and… BOOM! Found it!

The essence of the binary search algorithm is dividing in half, and comparing the number in the middle against the number you’re looking for. Based on this comparison, you select either the left or the right half, and start over again.

Let’s write some code to make that happen!

Binary search works because the input array is sorted. If the input array isn’t sorted, binary search won’t work. Moreover, binary search also only works for array values that can be compared, such as numbers. This doesn’t mean that you cannot use binary search for more complex values, such as objects, it just means those objects will need to have a unique numerical key (or index) you can search through. For example, searching for a primary key value in MySQL (a database tool) uses binary search.

Binary Search in Swift

Alright, let’s get started. First, we’re going to set up a function for our Swift code. Like this:

func binarySearch(in numbers: [Int], for value: Int) -> Int?
{

}

In the above code, you can see that the name of this function is binarySearch(in:for:). It has two named parameters, numbers of type [Int], and value of type Int. The return type is Int?, an optional, because we might not find a value. In other words, we’re going to search an array of integers for an integer, and optionally return an integer value (the index).

Next up, we’ll need some way to keep track of the left and right bounds of the array. Like this:

var left = 0
var right = numbers.count - 1

The left and right values correspond to the left and right bounds of the array. Initially, they’re set to the first and last index of the array. In the algorithm, we’re going to adjust these left and right indices to “wrap” the part of the array that we want to search. Don’t worry, you’ll see!

Then, we’re going to iterate over the array. We’ll use a while loop for that. We don’t know exactly how many iterations we’ll need, so we cannot use for in.

Like this:

while left <= right {

}

Here’s how that works:

For as long as right is greater than or equal to left, keep on iterating
When right is equal to left, the slice of the array we’re looking at is empty, and the while loop stops
We obviously need to change left and right inside the loop’s body, otherwise it’ll keep looping forever…

Then, inside the while loop, we’re doing this:

let middle = Int(floor(Double(left + right) / 2.0))

There it is! The code to calculate the middle index of the array. Here’s how it works:

Add left to right
Divide by 2
Round down with floor()

The above code uses the Int() and Double() initializers to transform the result of the equation to the right variable types. The floor() function works with Double values, but the type of middle needs to be Int.

You can imagine that, as the left and right bounds are going to change, we’ll keep on finding the middle of that slice of the array. It doesn’t matter which part of the array we’re getting — the above code will keep on finding its middle index.

Then, finally, the heart of the algorithm. Below the previous code, we’re adding this:

if numbers[middle] < value {
    left = middle + 1
} else if numbers[middle] > value {
    right = middle - 1
} else {
    return middle
}

What’s going on there? Here’s what:

First, check if the number in the middle of the array is smaller than the value we’re looking for. If it is, change the left bound into the middle index of the array plus one.
(If the previous clause was false.) Check if the middle number is bigger than the value we’re looking for. If it is, change the right bound into the middle index of the array minus one.
(If the previous clause was false.) Finally, if none of the above are true, simply return middle. The only option that’s remaining, is that middle is equal to the middle number. And when they’re equal, we’ve found the value, and thus the index, we’re looking for!

This is perhaps the most complex part of the algorithm to grasp, so let’s break it down. First, you need to understand that we’re comparing the middle number in the array against the number we’re trying to find. This can have 3 outcomes:

The middle number is smaller than the number we’re looking for
The middle number is bigger than the number we’re looking for
The middle number is equal to the number we’re looking for

The last outcome is the easiest. When the middle number is equal to the number we’re looking for, we’ve found the number we’re looking for! We’re returning middle, which is the index of that number. DONE!

In the other two cases, we need to change the slice of the array we’re looking at next. Remember that the array of numbers is sorted. So, we can safely say that:

If the middle number is smaller than the number we’re looking for, we need to look at the right of the array next. After all, the number we’re looking for must be in the right half of the array, because it’s bigger than the middle number!
If the middle number is bigger than the number we’re looking for, we need to look at the left of the array next. After all, the number we’re looking for must be in the left half of the array, because it’s smaller than the middle number.

Take a look at the diagram below again:

We’re searching for 13, right? In the first step, we’ve found that the middle number is 11. The number 11 is smaller than 13, which means that we’ll find number 13 in the right half of the array.

So, what about those left and right values? They help us manage the left and right bounds of the “slice” of the array we’re looking at. Initially, this is the entire array.

But then, after the first step, we’ve decided to look at the right half of the array. How do we change left or right to reflect that value?

Here’s how:

The left value is changed to middle + 1, because in the next iteration, we’re going to start looking from the middle of the array and onwards
The right value is kept the same, because we’re looking at numbers until the end of the array

In the second step, the exact opposite happens. We’ve started out looking at the entire right half of the array. The middle number in that right half is 19, and 19 is bigger than 13, so now we must look at the left part of that right part. Are you still with me?

Here’s how we change left and right:

The left value is kept the same, because the left bound doesn’t change
The right value is set to middle - 1, because the right bound is now the number before the middle; before 19

In the last step, we’re calculating the middle index, and we find out that its value is exactly the same as the number we’ve been looking for. The else clause of the above code block is invoked, and we’re returning middle, which is the index of the found number.

And last but not least, we need to incorporate some code that returns nothing when the number isn’t found. On the last line of the function, outside the while loop, we’re adding this:

return nil

This code is reached when the while loop has finished executing, but hasn’t found a number. Awesome!

Wrapping Up Binary Search

Pfew! That’s quite a bit of code, right? Here’s what we’ve come up with:

func binarySearch(in numbers: [Int], for value: Int) -> Int?
{
    var left = 0
    var right = numbers.count - 1

    while left <= right {

        let middle = Int(floor(Double(left + right) / 2.0))

        if numbers[middle] < value {
            left = middle + 1
        } else if numbers[middle] > value {
            right = middle - 1
        } else {
            return middle
        }
    }

    return nil
}

Let’s put it to good use. Can we find the index for number 13?

let numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
let value = 13

if let index = binarySearch(in: numbers, for: value) {
    print("Found \(value) at index \(index)")
} else {
    print("Did not find \(value)")
}

// Output: Found 13 at index 5

If you want, you can try out the code below. It’ll output what it’s doing, thanks to some print() statements, so you can see what’s going on inside the algorithm.

func binarySearch(in numbers: [Int], for value: Int) -> Int?
{
    var left = 0
    var right = numbers.count - 1

    while left <= right {

        let middle = Int(floor(Double(left + right) / 2.0))

        print("Looking for \(value) in \(numbers[left...right])")
        print("Middle index is \(middle), value is \(numbers[middle])")

        if numbers[middle] < value {
            print("\(numbers[middle]) is smaller than \(value), choosing right half of array")
            left = middle + 1
        } else if numbers[middle] > value {
            print("\(numbers[middle]) is bigger than \(value), choosing left half of array")
            right = middle - 1
        } else {
            return middle
        }
    }

    return nil
}

See that numbers[left...right] bit, in the code? It’s using the range operator ... to get a slice of the array. And it’s using those left and right bounds! You can see in the output how we’re using those bounds to select sections of the array. Neat!

If you want to expand the binarySearch(in:for:) function to include any type that’s logically comparable, then change its signature into:

func binarySearch<T: Comparable>(in numbers: [T], for value: T) -> Int?

The function now uses generics to accept input for any type that conforms to the Comparable protocol, such as integers and doubles.

The big question is, of course, whether binary search is more efficient than our naive, linear approach. Yes, yes it is! The time complexity of binary search is O(log n), also called logarithmic time.

Here’s why: for every step that the algorithm takes, the number of remaining steps is reduced logarithmically.

In other words, if the input array is twice as big, we only have to take one more step to find a number in it. Compared to the naive approach, in O(n), that same array would take twice the amount of work!