Binary Search Array Extension in Swift

      7 Comments on Binary Search Array Extension in Swift

There are more than a few search algorithms. Today we’ll examine one of them, the Binary Search Algorithm, and we’ll implement this algorithm using an array extension in swift. We’ll also compare the performance of this algorithm to your standard brute force search, and see how it compares.

Binary Search Algorithm

Binary search is one of the logarithmic algorithms, in worst case it will run in O(log n) where n is the size of the array you’re searching. If you implement a search using a brute force method, where you would use a for loop, worst case complexity would be O(n). So with just a little code we can gain a lot of performance.

Usually the binary search is implemented using a tree structure, so it’s often called a binary search tree. Binary search tree consists of nodes, where each node has two children, left child, and a right child. Value in the left child is less than the value in the parent, and the value in the right child is greater than the value in the parent. As you would imagine, searching for the value is quite trivial, you examine the value in the current node, if the value is equal, great, you have a search hit, if the value is smaller, you move on to the left child, and if the value is greater you move on to the right child. This is a recursive function, so you do the same comparison for the child.

We can also perform a binary search on a standard sorted array (please note, the array must be sorted). You take your array, and check the middle element, if the value you’re searching for is less than the value of the middle element you will examine the left side of the array, if it’s greater, you will examine the right side. Let’s follow this with an example depicted on the following image:

On the graphic above, we have an array of 11 elements, and we’re searching for the number 13. Blue elements are our edges of the subarray (Min and Max), red element is the middle element of the subarray, and green element is our search hit. In the first iteration our Min element is the first element of the array, Max is the last element of the array and Mid is the middle element. We compare the middle element with our target (number 13). Target is less than the Mid element, so we move to the left subarray. Now, in the second iteration, the Min remains the same, the Max is the old Mid (number 55), and the new Mid is the middle of the new subarray (number 7). We compare the target with the new Mid element, the target is greater than 7, so we move to the right subarray. Now our new Min is the old Mid, and the Max remains the same. New Mid is the middle of the new subarray. In the third iteration we compare the Mid with the target, and we see that they match, so we have our search hit. We found our value in 3 iterations.

As you can see, the algorithm is pretty simple, so let’s move on to the code.

Implementation

To implement this algorithm in swift we’ll create an extension on the Array type, like so:

extension Array where Element: Comparable {
    
    func search(element: Element) -> Int? {
        
        var low = 0
        var high = count - 1
        var mid = Int(high / 2)
        
        while low <= high {
            
            let midElement = self[mid]
            
            if element == midElement {
                return mid
            }
            else if element < midElement {
                high = mid - 1
            }
            else {
                low = mid + 1
            }
            
            mid = (low + high) / 2
        }
        
        return nil
    }
}

Believe it or not, this is it. The whole algorithm. If you follow the description of the algorithm in the previous paragraph, you’ll see that the implementation follows it exactly. We’ll be testing this algorithm using String data type, but with this extension you can use it with any Comparable type, so you should be able to use it in your apps without any problems.

Testing

In our unit tests we will create an array of random strings, and we will append our target string at the end, the we will sort the array, and perform our search using the binary search, and the brute force method. I’ve create a small extension on the String class that generates a random string of a specified length, like so:

extension String {
    
    static func randomString(length: Int) -> String {
        let characters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
        
        var result = ""
        
        for _ in 0..<length {
            let randomIndex = Int(arc4random_uniform(UInt32(characters.characters.count)))
            let characterIndex = characters.index(characters.startIndex, offsetBy: randomIndex)
            result += String(characters[characterIndex])
        }
        
        return result
    }
}

And our test method is pretty simple:

    private func runWithMaxElements(maxElements: Int) {
        
        print("================== Testing search with \(maxElements) elements ==================")
        
        var strings = randomStringArray(maxElements: maxElements)
        strings.append("Test String")
        strings.sort()
        
        print("Sequential Search:")
        var stopwatch = Stopwatch()
        var index: Int?
        for i in 0..<strings.count {
            if strings[i] == "Test String" {
                index = i
                break;
            }
        }
        stopwatch.printElapsedTime()
        XCTAssertNotNil(index)
        
        print("Binary Search:")
        stopwatch = Stopwatch()
        let searchIndex = strings.search(element: "Test String")
        stopwatch.printElapsedTime()
        XCTAssertNotNil(searchIndex)
    }

So, let’s examine our test results.

Results

Let’s see the data in a chart:

And the table with the data (values are in milliseconds):

1k 10k 100k 1M
Sequential Search 22 56 65 72
Binary Search 12 18 14 11

We can see from the data that the values for the sequential search are increasing linearly, while the values for the binary search are more or less the same (around 15ms).

Conclusion

If you need to search through a lot of data, it might be a good investment to implement this simple array extension. The benefits you’ll see might be pretty huge. The values we saw were measured on my mac, meaning, on the actual device they would be greater. So, benefits might be obvious even for smaller data sets. I hope this article will help you in some way, or at least give you an inspiration on how to solve a search problem that you might be facing.

As always, have a nice day 🙂

Dejan.

More resources

Changelog
  • 7 Aug 2018 – Fixed boundary issue in the code listing (thanks: Vitaly)

7 thoughts on “Binary Search Array Extension in Swift

  1. Dejan Agostini Post author

    You’re absolutely right Vitaly. If you’re searching though an array that has only one element, and the element you’re searching for is not in the array it will run into a loop. I made a mistake with setting the bounds in the code. Thanks a lot for pointing it out. I’ve fixed the code above and gave you credit for the fix in the changelog. I appreciate the help 🙂

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.