Implement Binary Search in Swift

Photo by Nikola Majksner on Unsplash

In computer science, there are two types of algorithms commonly used to solve a problem searching and sorting algorithms. Its valuable to know which algorithm to use to perform a computation.In this tutorial, we will focus on searching algorithms.

When we talk about searching algorithms the use of binary search algorithm is very common. It is a very simple algorithm used to find a value within a sorted array.How binary search algorithm works?

How binary search algorithm works?

In binary search, we find specific value in sorted array by comparing that value to mid element of array. If value matches the mid element of array it returns the position from array. If value is less than mid element of array, then we search the left half of array. If value is greater than mid element of array, then we search the right half of array. We repeat this process until we either find a target or if subarray size is 0 then value is not in array.

Implement binary search in Swift

Now we will implement binary search step by step.

1. First of all, choose sorted array to search for

var arrayToSearch = [2,5,8,9,10,12,16]

2. Now choose target value to search in sorted array

var valueToFind = 10

3. Set low index and highIndex

var lowIndex = 0
var highIndex = arrayToSearch.count - 1

4. Create a function for performing binary search with two parameters, array of type [Int] and key of type Int. The function has return type Int? an optional type

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

}

5. Now we will iterate over array using while loop. It will iterate until lowIndex is lower or equal than highIndex

while lowIndex <= highIndex {

}

6. Set position of middle element of array

let mid = (lowIndex + highIndex) / 2

7. If mid element of array matches target key than return mid element position

if array[mid] == key {
    return mid
}