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:
- Take the midpoint and compare it with the item we are looking for
- If it’s equal to the midpoint, then return it
- If it’s less than the middle, we search the left side; if it’s larger than the middle, we search the right side.
- 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)