20. Binary Search

Written by Kelvin Lau

Binary search is one of the most efficient searching algorithms with time complexity of O(log n). This is comparable with searching for an element inside a balanced binary search tree.

Two conditions that need to be met before binary search may be used:

• The collection must be able to perform index manipulation in constant time. This means that the collection must be a RandomAccessCollection.
• The collection must be sorted.

Example

The benefits of binary search are best illustrated by comparing it with linear search. Swift’s Array type uses linear search to implement its firstIndex(of:) method. It traverses through the whole collection or until it finds the first element:

Binary search handles things differently by taking advantage of the fact that the collection is already sorted.

Here’s an example of applying binary search to find the value 31:

Instead of eight steps to find 31, it only takes three. Here’s how it works:

Step 1: Find middle index

The first step is to find the middle index of the collection. Finding it is fairly straightforward:

Step 2: Check the element at the middle index

The next step is to check the element stored at the middle index. If it matches the value you’re looking for, return the index. Otherwise, continue to Step 3.

Step 3: Recursively call binary search

The final step is to call the binary search recursively. However, this time, you’ll only consider the elements exclusively to the left or to the right of the middle index, depending on the value you’re searching for. If the value you’re searching for is less than the middle value, you search the left subsequence. If it is greater than the middle value, you search the right subsequence.

Each step effectively removes half of the comparisons you would otherwise need to perform.

In the example where you’re looking for the value 31 (which is greater than the middle element 22), you apply binary search on the right subsequence:

You continue these three steps until you can no longer split up the collection into left and right halves or until you find the value inside the collection.

Binary search achieves an O(log n) time complexity this way.

Implementation

Open the starter playground for this chapter. Create a new file in the Sources folder named BinarySearch.swift. Add the following to the file:

// 1
public extension RandomAccessCollection where Element: Comparable {
  // 2
  func binarySearch(for value: Element, in range: Range<Index>? = nil)
      -> Index? {
    // more to come
  }
}

Things are relatively simple so far:

1. Since binary search only works for types that conform to RandomAccessCollection, you add the method in an extension on RandomAccessCollection. This extension is constrained as you need to be able to compare elements.
2. Binary search is recursive, so you need to pass in a range to search. The parameter range is optional, so you can start the search without specifying a range. In this case, where range is nil, the entire collection will be searched.

Next, implement binarySearch as follows:

// 1
let range = range ?? startIndex..<endIndex
// 2
guard range.lowerBound < range.upperBound else {
  return nil
}
// 3
let size = distance(from: range.lowerBound, to: range.upperBound)
let middle = index(range.lowerBound, offsetBy: size / 2)
// 4
if self[middle] == value {
  return middle
// 5
} else if self[middle] > value {
  return binarySearch(for: value, in: range.lowerBound..<middle)
} else {
  return binarySearch(for: value, in: index(after: middle)..<range.upperBound)
}

Here are the steps:

1. First, you check if range was nil. If so, you create a range that covers the entire collection.
2. Then, you check if the range contains at least one element. If it doesn’t, the search has failed, and you return nil.
3. Now that you’re sure you have elements in the range, you find the middle index in the range.
4. You then compare the value at this index with the value that you’re searching for. If the values match, you return the middle index.
5. If not, you recursively search either the left or right half of the collection.

That wraps up the implementation of binary search! Head back to the playground page to test it out. Write the following at the top of the playground page:

let array = [1, 5, 15, 17, 19, 22, 24, 31, 105, 150]

let search31 = array.firstIndex(of: 31)
let binarySearch31 = array.binarySearch(for: 31)

print("firstIndex(of:): \(String(describing: search31))")
print("binarySearch(for:): \(String(describing: binarySearch31))")

You should see the following output in the console:

index(of:): Optional(7)
binarySearch(for:): Optional(7)

This is the index of the value you’re looking for.

Binary search is a powerful algorithm to learn and comes up often in programming interviews. Whenever you read something along the lines of “Given a sorted array…”, consider using the binary search algorithm. Also, if you are given a problem that looks like it is going to be O(n²) to search, consider doing some up-front sorting so you can use binary searching to reduce it down to the cost of the sort at O(n log n).

Key points

• Binary search is only a valid algorithm on sorted collections.
• Sometimes, it may be beneficial to sort a collection to leverage the binary search capability for looking up elements.
• The firstIndex(of:) method on sequences uses linear search, with O(n) time complexity. Binary search has O(log n) time complexity, which scales much better for large data sets if you are doing repeated lookups.