Understanding and implementing binary search in swift

Binary search or (divide and conquer) is one of the most popular and widely adopted algorithms for searching a data structure because of its efficiency and speed.

I will be showing you how to implement a search algorithm using the binary search (divide and conquer) method, this method of search is what is mostly used under the hood of Apple's standard library API's for search searching items i.e. the first(where: ) last(where: ) firstIndex(where: ) lastIndex(where: ) and more.

The Problem

Let's say we have an array of 12 random numbers and would like to find 30 from this list of numbers but you don't know which index the favorite number of yours appears in the list. To solve this problem start by asking how many times do I have to look inside this array of numbers before I end up with my favorite number? Given that you know how to use loops to traverse an array and print its element, you would think to combine for loop and if statement on the list of numbers to find and print any index whose value is your favorite number 30

let numbers = [20, 4, -2, 0, 1, 40, 50, 60, 10, 30, 90, 70]
let myFavorite = 30

for (index, value) in numbers.enumerated() {
    if value == myFavorite {
        print("Index for favourite is: ",index)
        break
    }
}

Index for favorite is: 9

While this may put a smile on your face knowing that you have successfully found the index for your favorite number and you only had to look 10 times

But think what if this list of numbers is 10Billion in length and your favorite number is at the very end of the list, woof! This would take 10Billion times of looking into the array of numbers, imagine if this was a person trying to individually look inside 10Billion boxes that would take more than a lifetime to complete but of course computers are way faster than a human and would complete the task in a shorter amount of time compared to a human but longer than it took when the list was only 12 items. This will make you angry especially when you need your favorite number ASPA and don't have time to wait for this 10Billion loop to complete.

Binary search can help reduce your wait time to a significant amount but only with one requirement from you. The list of numbers must be sorted (arranged in order). Binary search can only work on a list that is sorted, so it is a requirement that your list of numbers must be sorted. See the search algorithm post on how to sort a list of items if you'd like to find out how we're able to sort the numbers.

Binary search

Start by asking yourself how many times do I have to divide 10Billion by 2 until the final answer is 0? The answer is 34 times which is not too many and not 10Billion times. 34 times is the worst case (The longest wait time) for a 10Billion list of numbers The maximum time we have to look inside the list to find our favorite number.

How it works

Binary search works by first taking the total length of the array and divides it into two parts left and right where left represents the first index of numbers which is 0 and right represents the last index of numbers which is (n-1) or (numbers.count - 1). The outcome of this operation is called the middle and it represents the middle index of numbers.

let numbers = [-2, 0, 1, 4, 10, 20, 30, 40, 50, 60, 70, 90] //sorted
var left = 0
var right = numbers.count - 1
var middle = (left + right) / 2

The next thing is to take the value of the middle which is 5 in this case and look inside the numbers list for our favorite number using the middle index value.

If the value in the middle index corresponds to our favorite number we return it and we are done but if not we will check if the value in the middle index is bigger than our favorite number (remember that our number is sorted) if yes then there is no need to look at any index below our current middle index, which mean we are only concerned with the indexes above our current middle index which it to the right and we have just saved ourselves the huddles of looking it 4 boxes.

Now that we have chosen to look at the boxes below our middle index, we have to update the value of left because it is no longer 0 but now middle + 1 the reason why we are adding 1 to the middle is that we have already looked into and it doesn't have our favorite number and there is no reason to include it again and vice versa

let myFavourite = 30

if numbers[middle] == myFavourite {
    print("Yes Found! Your favourite number at index: \(middle) \n")
    
} else if numbers[middle] < myFavourite {
    print("The middle index \(middle) with value:  \(numbers[middle]) is too small")
    print("Please update left to: \(middle + 1) \n")
}else {
    print("The middle index \(middle) with value:  \(numbers[middle]) is too large")
    print("Please update right to: \(middle - 1) \n")
}

The middle index 5 with value: 20 is too small

Please update left to: 6

You might be thinking that now is the best time to bring it the loop and perform these operations, again and again, until the favorite number index is found and yes you're correct.

Let's perform the operations with a loop and update the value of the middle index inside the loop each time to loop runs until he has completed the runs.

The diagram below shows the steps our algorithm is going to perform until the loop life cycle is completed or our favorite number is found.

Binary search diagram
let numbers = [-2, 0, 1, 4, 10, 20, 30, 40, 50, 60, 70, 90] //sorted
var left = 0
var right = numbers.count - 1
var middle = 0

while left <= right {
    
    middle = (left + right) / 2
    
    if numbers[middle] == myFavourite {
        print("Found! Your favourite number at index: \(middle) with value: \(numbers[middle]) \n")
        break
        
    } else if numbers[middle] < myFavourite {
        print("The middle index \(middle) with value:  \(numbers[middle]) is too small")
        print("Please update left to: \(middle + 1) \n")
        
        left = middle + 1
        
    }else {
        print("The middle index \(middle) with value:  \(numbers[middle]) is too large")
        print("Please update right to: \(middle - 1) \n")
        
        right = middle - 1
    }
}

The middle index 5 with value: 20 is too small

Please update left to: 6

The middle index 8 with value: 50 is too large

Please update right to: 7

Found! Your favourite number at index: 6 with value: 30

Notice that left is now 6 and right is 7 and mid is now (6 + 7) / 2 which is 6 and 6 is the correct index for our favourite number.

Awesome! It only took three (3) lookups to finally located our favorite number.

Now let's write a function combined with the power of swift features to write a clean version of a binary search algorithm.

/// This binary search function will accept an array of items of type Int
/// and also a search value, It will then search for the index of
/// that value in the items and return the index if found or nill if not found
func binarySearch(for value: Int, in items: [Int]) -> Int? {

    var left = 0
    var right = items.count - 1
    var mid = 0
    
    
    while left <= right {
        mid = (left + right) / 2
        
        if items[mid] == value {
            return mid
            
        } else if items[mid] < value {
            left = mid + 1
            
        } else  {
            right = mid - 1
        }
    }
    
    return nil
}

Now let's test our binary search function

let numbers = [-2, 0, 1, 4, 10, 20, 30, 40, 50, 60, 70, 90] //sorted
let myFavourite = 30

if let index = binarySearch(for: myFavourite, in: numbers) {
    print("Index Found: \(index)")
} else {
    print("Your favourite number is: \(myFavourite) not in the numbers")
}


let myFavouriteTwo = 14
if let index = binarySearch(for: myFavouriteTwo, in: numbers) {
    print("Index Found: \(index)")
} else {
    print("Your favourite number is: \(myFavouriteTwo) not in the numbers")
}

Index Found: 6

Your favourite number: 14 is not in the numbers

We have successfully created a binary search function. I hope you enjoyed the reading. Please report any typos and questions to me I will be delighted to answer those. Thanks for reading!