How to Perform a Binary Search in Swift

The basic idea behind a binary search is that you take the midpoint of a sorted array and compare that with the item you’re searching for. The key thing to remember is that the array must be sorted. The steps are:

1. Take the midpoint and compare it with the item we are looking for
2. If it’s equal to the midpoint, then return it
3. If it’s less than the middle, we search the left side; if it’s larger than the middle, we search the right side.
4. Repeat that until we find the element

This lends itself nicely to recursion. Here’s a basic Swift implementation:

// Return the element if found; otherwise nil
func binarySearch(sortedArray: [Int], elementToFind: Int) -> Int? {
    let midPointIndex = sortedArray.count / 2
    let midPoint = sortedArray[midPointIndex]
        
    // We found it
    if elementToFind == midPoint {
        return elementToFind
    }
    
    // If we haven't found it by now, it's not in the array
    if sortedArray.count < 2 {
        return nil
    }
    
    // Keep looking
    if elementToFind < midPoint {
        let newArray = Array(sortedArray[..<midPointIndex])
        return binarySearch(sortedArray: newArray, elementToFind: elementToFind)
    } else {
        let newArray = Array(sortedArray[midPointIndex...])
        return binarySearch(sortedArray: newArray, elementToFind: elementToFind)
    }
}

let sortedArray = [2, 3, 7, 8, 10, 13, 14, 18, 22]
let elementToFind = 10

let found = binarySearch(sortedArray: sortedArray, elementToFind: elementToFind)
print(found)