The binary search is the one of the fastest searches you can perform to find an element in a sorted array, typically ascending in order. Lets first take a look at how a binary search works and implement it in Swift.

How a binary search works

Lets look at the following sorted array, we want to find the number 7.

We set a pointer to the start, middle and end. We get the middle pointer by getting the size of the array and dividing it by two. So our array size is 7. Divided by two that is 3.5, Swift rounds this down to 3. So the middle is position 3 in the array (Remember the first element of an array is position 0)

Now we check if the middle element 11 is the value we are searching for. 11 is not equal to 7 so we go on to the next step:

• If 11 is greater then 7 we only search the left side of the array, as it is sorted we know 7 will be in there somewhere
• If 11 is less then 7 we only search the right side of the array, as it is sorted we know 7 will be in there somewhere.

In this example 11 is less then 7, so it has to be somewhere to the left of 11.

Since its on the left side we move the end to the element before 11, which is 9. Then we find the middle off the array again which is 3/2 = 1 (Remember swift rounds down 1.5). Position 1 in the array is 7

Now we repeat the steps above again, is the middle element of the array the value we are searching for? Yes it is, we are looking for 7. So we stop the search and return the we found 7. If we did not find 7 we would repeat halving the array on either the left or right side until we either find the value, or there is nothing left to search in which case it is not in the array.

Implementing it in Swift

Now lets implement it in Swift, the comments outline the steps taken as outlined above to find the value.

func binarySearch(_ a: [Int], key: Int) -> Int? {
    var lowerBound = 0 // The start of the array
    var upperBound = a.count // The end of the array
    // If we still have elements to search for in the array
    while lowerBound < upperBound {
        // Get the middle of the array
        let midIndex = lowerBound + (upperBound - lowerBound) / 2
        // If middle of array is the value we are searching for return it
        if a[midIndex] == key {
            return midIndex
        // Otherewise if the middle element is less then the value search the right side of the array
        } else if a[midIndex] < key {
            lowerBound = midIndex + 1
        // Otherewise if the middle element is greater then the value search the left side of the array
        } else {
            upperBound = midIndex
        }
    }
    // If we dont find the value we are searching for return nil
    return nil
}

binarySearch([1,7,9,11,12,15,19], key: 7)

Then we can call binary search and it will return 1, which is the position for 7.

Now this is all well and good, however this can only search for Int types, what if we wanted to search through and array of doubles? Or other data types that can be compared?

Lucky in Swift we can with the power of generics! If you are not familar with generics, check out the article by Apple here. It basically allows the function to accept multiple data types such as Int’s and Doubles, however they all must be the same data type for each argument (a, and key). To do this change this line:

func binarySearch(_ a: [Int], key: Int) -> Int? {

to:

func binarySearch<T: Comparable>(_ a: [T], key: T) -> Int? {

Now we can call binrarySearch with decimal numbers (Doubles)

binarySearch([1.2, 2.2, 3.4], key: 1.2)

As you can see generics are quite powerful when you write a function that can be reused for several different data types.