# Play With Code: Binary Search in 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!

## Further Reading

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: