Become a professional iOS developer
Get started with iOS 13 and Swift 5
Sign up for my iOS development course to learn iOS development with Swift 5, and start your professional iOS career.
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 article, 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.
Imagine you’ve got a sequence 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.
Sign up for my iOS development course to learn iOS development with Swift 5, and start your professional iOS career.
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?
Here’s how:
11
at index 4
. We can calculate the middle item by taking the last index, dividing it by 2, and rounding that down (“floor”).11
is smaller than 13
, so we’re continuing with the right half of the array (and forget the left half).19
at index 7
. (You’ll see in the code, later on, how we’re calculating that middle index.)19
is bigger than 13
, so now we’re continuing with the left half of the remaining array (and forget the right half).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 core 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.
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, because we don’t know exactly how many iterations we’ll need. Like this:
while left <= right {
}
Here’s how that works:
right
is greater than or equal to left
, keep on iteratingwhile
loop stopsleft
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:
left
to right
2
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:
left
bound into the middle
index of the array plus one.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.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 understand, 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 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:
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 subsection 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:
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 onwardsright
value is kept the same, because we’re looking at numbers until the end of the arrayIn 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
:
left
value is kept the same, because the left bound doesn’t changeright
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!
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!
Sign up for my iOS development course to learn iOS development with Swift 5, and start your professional iOS career.
Awesome! You’ve mastered the binary search algorithm in Swift. We’ve gotten to the core: chopping arrays in half, and comparing their middles against the number we’re looking for.
Want to learn more? Check out these resources:
Hi, I'm Reinder.
I help developers play with code.