A new day, a new algorithm. Today I'd like to go over binary search, or divide and conquer.
Introduction
When you're looking for an item in a sorted array, binary search can drastically reduce the number of steps required. Instead of searching through an array one element at a time, like with Linear Search, you split it into pieces. Here's how that works:
- Inspect the element in the middle of the array - is it less than, greater than, or equal to the value we're searching for?
- If the middle value is equal to our search value, we're finished!
- If the middle value is less than our search value, narrow our search down to the last half of the array (from index m to index n, where m is the index of the middle item, and n is the index of the last item)
- If the middle value is greater than our search value, narrow our search down to the first half of the array (from index 0 to index m, where m is the index of the middle item)
- Repeat steps 1-4 until either A) the search value is found, or B) the array cannot be split any further, which means the search value was not found in the array.
To help illustrate this, here's an image of the flow:

Swift Implementation
Here's one way to implement this algorithm recursively in Swift:
func binarySearch<T: Comparable>(a: [T], key: T, range: Range<Int>) -> Int? {
guard range.startIndex < range.endIndex else {
// If the start index is larger than or equal to the
// end index, then we've reached the point where the search key
// could not be found
return nil
}
// Find the middle point in the array within the given range
let midIndex = range.startIndex + (range.endIndex - range.startIndex) / 2
if a[midIndex] > key {
// Is the search key in the left half?
return binarySearch(a, key: key, range: range.startIndex ..< midIndex)
} else if a[midIndex] < key {
// Is the search key in the right half?
return binarySearch(a, key: key, range: midIndex + 1 ..< range.endIndex)
} else {
// We found our search key - return the index!
return midIndex
}
}
let list: [Int] = [1, 2, 4, 5, 8, 9, 11, 22, 23, 28, 32, 44]
let indexOfTwentyTwo = binarySearch(list, key: 22, range: 0 ..< list.count)And, if you'd like to clean up your call stack a little, here's an implementation without recursion:
func binarySearch<T: Comparable>(a: [T], key: T) -> Int? {
var range = 0..<a.count
while range.startIndex < range.endIndex {
// Find the middle point in the array within the given range
let midIndex = range.startIndex + (range.endIndex - range.startIndex) / 2
if a[midIndex] == key {
// If we found our search key, return the index
return midIndex
} else if a[midIndex] < key {
// If the mdidle value is less than the key, look at the right half
range.startIndex = midIndex + 1
} else {
// If the midle value is greater than the key, look at the left half
range.endIndex = midIndex
}
}
return nil
}binary-search-non-recursive.swift on GitHub
When To Use Binary Search
Binary search is an incredibly fast search algorithm at O(log n). Unfortunately, it relies on the array being sorted, so you have to weigh the advantages of a O(log n) search algorithm with the time required to sort your array.
If you already have a sorted array, or if you're sorting an array once and searching multiple times, binary search is probably your best bet.
References
The open source Swift Algorithm Club repository provided much of the explanation here - if you haven't had a chance to check it out, you should!