Swift Algorithms. Binary Search

How to solve following task: find element in the array. For this task we can use linear search algorithm - simply iterate over each element of the array until target element is found.

Linear Search

Unsorted array of integers.

let array = [45, 42, 75, 61, 37, 95, 30, 19, 81, 77, 44, 54, 8, 88, 85, 46, 39, 35, 65, 3]

Algorithm of linear search.

func linearSearch(array: [Int], target: Int) -> Bool {
    for i in 0..<(array.count - 1) {
        if array[i] == target {
            return true
        }
    }
    return false
}

Test results.

linearSearch(array: array, target: 65) // true
linearSearch(array: array, target: 68) // false
assert(true == linearSearch(array: array, target: 65), "Error happened")
assert(false == linearSearch(array: array, target: 68), "Error happened")

Time Complexity of Linear Search is O(n).

Binary Search Algorithm

How we can increase time from linear search? The solution is using of Binary Search. The main idea is to splitting the array by half until the target is found. But there is one requirement - array must be sorted.

Steps of Binary Search algorithm is following:

1. Split the array by half and define whether the target, in the left half or in the right half.
2. If the target is in the left half, you repeat the process there: split the left half into two even smaller pieces and look in which piece the target is. (The same for the case when it's the right half.)
3. These steps repeats until the target is found. If the array cannot be split one more time, it means that target is not in the array

Time Complexity

What is the time complexity of Binary Search. How express what number of operations that required to find target in array? For example, there is array with 1000 elements, how many time we need to divide 1000 by 2 to get 1 value?

1000 / 2

500 / 2

250 / 2

125 / 2

65 / 2

33 / 2

17 / 2

9 / 2

5 / 2

3 / 2

1

Or it can be expresses as how many times we need to multiply 1 by 2 to get 1000?

N = 1*2ˆK 

It gives us the following K = logN, because logN is the number of times we need to raise 2 to the power of K to get N.

So, for finding target in array of 1000 elements we need maximum 9 operations instead of 1000 for linear search.

Recursive Implementation

Let's provide recursive implementation of Binary Search. There is entry point.

func binarySearch(array: [Int], target: Int) -> Bool {
    let left = 0
    let right = array.count - 1
    return binarySearchRecursive(array: array, target: target, left: left, right: right)
}

There is recursive function.

func binarySearchRecursive(array: [Int], target: Int, left: Int, right: Int) -> Bool {
    if left > right {
        return false
    }
    let midIndex = (left + right) / 2
    let midValue = array[midIndex]
    if midValue == target {
      return true
    } else if (target > midValue) {
        let newLeft = midIndex + 1
        return binarySearchRecursive(array: array, target: target, left: newLeft, right: right)
    } else {
        let newRight = midIndex - 1
        return binarySearchRecursive(array: array, target: target, left: left, right: newRight)
    }
}

Test results.

let sortedArray = [3, 8, 19, 30, 35, 37, 39, 42, 44, 45, 46, 54, 61, 65, 75, 77, 81, 85, 88, 95]
binarySearch(array: sortedArray, target: 88) // true
binarySearch(array: sortedArray, target: 89) // false
assert(true == binarySearch(array: sortedArray, target: 88), "Error happened")
assert(false == binarySearch(array: sortedArray, target: 89), "Error happened")

Problem with overflow

There is one thing that can cause error. The expression let midIndex = (left + right) / 2 could fail because of overflow when left and right are close to the max values of type Int.  To prevent his situation we can present this expression through difference between right and left. Algorithm is following:

1. midIndex = (left + right) / 2
2. (left + right) / 2 = (left + left - left+ right + right - right) / 2
3. (left + left - left+ right + right - right) / 2 = (right - left + 2*left + (right - right)) / 2
4. (right - left + 2*left + (right - right)) / 2 = (right - left + 2*left) / 2
5. (right - left + 2*left) / 2 = (right - left) / 2 + left

So, we will replace this unsafe calculation of mid index

let midIndex = (left + right) / 2

to this safe calculation

let midIndex = left + (right - left) / 2

update algorithm

func binarySearchRecursive(array: [Int], target: Int, left: Int, right: Int) -> Bool {
    if left > right {
        return false
    }
    let midIndex = left + (right - left) / 2
    let midValue = array[midIndex]
    if midValue == target {
      return true
    } else if (target > midValue) {
        let newLeft = midIndex + 1
        return binarySearchRecursive(array: array, target: target, left: newLeft, right: right)
    } else {
        let newRight = midIndex - 1
        return binarySearchRecursive(array: array, target: target, left: left, right: newRight)
    }
}

With Range instead of Left and Right

Instead of two parameters left and right we can use one - range of type Range<Int>. Type range has two variable lowerBound and upperBound.

func binarySearchRecursive(array: [Int], target: Int, range: Range<Int>) -> Bool {
    if range.lowerBound >= range.upperBound {
        return false
    }
    let midIndex = range.lowerBound + (range.upperBound - range.lowerBound) / 2
    print(midIndex)
    let midValue = array[midIndex]
    if midValue == target {
        return true
    } else if (target > midValue) {
        let newRange: Range<Int> = (midIndex + 1)..<range.upperBound
        return binarySearchRecursive(array: array, target: target, range: newRange)
    } else {
        let newRange: Range<Int> = (range.lowerBound)..<midIndex
        return binarySearchRecursive(array: array, target: target, range: newRange)
    }
}

//let sortedArray = [3, 8, 19, 30, 35, 37, 39, 42, 44, 45, 46, 54, 61, 65, 75, 77, 81, 85, 88, 95]
binarySearchRecursive(array: sortedArray, target: 88, range: 0..<sortedArray.count) // true
binarySearchRecursive(array: sortedArray, target: 89, range: 0..<sortedArray.count) // false

Making Generic Function

We can make our function more universal by making it generic. Generic function can be applied to any array where elements are conform to protocol Comparable. For example, we can apply it to array of strings.

func binarySearchRecursive<T: Comparable>(array: [T], target: T, range: Range<Int>) -> Bool {
    if range.lowerBound >= range.upperBound {
        return false
    }
    let midIndex = range.lowerBound + (range.upperBound - range.lowerBound) / 2
    print(midIndex)
    let midValue = array[midIndex]
    if midValue == target {
        return true
    } else if (target > midValue) {
        let newRange: Range<Int> = (midIndex + 1)..<range.upperBound
        return binarySearchRecursive(array: array, target: target, range: newRange)
    } else {
        let newRange: Range<Int> = (range.lowerBound)..<midIndex
        return binarySearchRecursive(array: array, target: target, range: newRange)
    }
}

binarySearchRecursive(array: sortedArray, target: 81, range: 0..<array.count)
let strings = ["aa", "bb", "cc", "dd", "ee"]
binarySearchRecursive(array: strings, target: "dd", range: 0..<strings.count)

Iterative Implementation

Instead of using recursive calls we can implement Binary Search algorithm using iterative approach and while loop. On each iteration of loop we just will change lower or upper bounds of range.

func binarySearchIterative<T: Comparable>(array: [T], target: T) -> Bool {
    var lower = 0
    var upper = array.count
    while (lower <= upper) {
        let midIndex = lower + (upper - lower) / 2
        let midValue = array[midIndex]
        if midValue == target {
            return true
        } else if target > midValue {
            lower = midIndex + 1
        } else {
            upper = midIndex - 1
        }
    }
    return false
}

let sortedArray = [3, 8, 19, 30, 35, 37, 39, 42, 44, 45, 46, 54, 61, 65, 75, 77, 81, 85, 88, 95]
binarySearchIterative(array: sortedArray, target: 81) // true
binarySearchIterative(array: sortedArray, target: 82) // false

Making Extension

Now, using iterative solution that we provided above we can easily make extension for all Array where elements of array conform to Comparable protocol.

extension Array where Element: Comparable {
    
    func binarySearch(target: Element) -> Bool {
        var lower = 0
        var upper = self.count
        while (lower <= upper) {
            let midIndex = lower + (upper - lower) / 2
            let midValue = self[midIndex]
            if midValue == target {
                return true
            } else if target > midValue {
                lower = midIndex + 1
            } else {
                upper = midIndex - 1
            }
        }
        return false
    }
}

let sortedArray = [3, 8, 19, 30, 35, 37, 39, 42, 44, 45, 46, 54, 61, 65, 75, 77, 81, 85, 88, 95]
sortedArray.binarySearch(target: 81) // true
sortedArray.binarySearch(target: 82) // false

Source Code

Source code for this post could be found here on GitHub