Binary search in F#

While F# developers are blessed with a plethora of collections types and ways to access them, having a good understanding of data structures and algorithms empowers developers to tackle problems in a more efficient way. I'm going through A Common-Sense Guide to Data Structures and Algorithms to improve my core programming skills, and want to walk you through using F# to implement one of the core algorithms discussed. This is binary search in F#!

Binary search is a super fast search algorithm that works on ordered collections. It is so fast because at every check, it discards half of the possible values. If you compare this with naively going though all elements from start to finish (known as linear search), this makes a huge difference: with an array of 100 values, linear search can take up to 100 steps; binary search on the other hand will be there in at most 7.

Let's create a function for our algorithm:

let binarySearch (value: 'a) (toSearch: 'a array) =

Because we have a step that we want to repeat multiple times, we will introduce a recursive function that takes the upper bound and lower bound of our search. We also need to call this function directly in the binarySearch function, passing it the highest and lowest index of our array as the upper and lower bounds.

let binarySearch (value: 'a) (toSearch: 'a array) =
    let rec recurse (lowerBound: int) upperBound =
        //TODO
    recurse 0 (Array.length toSearch - 1)

Every search attempt, we compare the middle value of the range we are checking with the value we are trying to find:

• If the middle value is higher than what we try to find, we recurse, placing our upper bound just below the middle value.
• If the middle value is lower than what we try to find, we recurse, placing our lower bound just above the middle value.
• If neither is true, we found our value! We can return it.

let binarySearch (value: 'a) (toSearch: 'a array) =
    let rec recurse lowerBound upperBound =
        let midPoint = (upperBound + lowerBound) / 2
        let midValue = toSearch[midPoint]

        if midValue > value then
            recurse lowerBound (midPoint - 1)
        else if midValue < value then
            recurse (midPoint + 1) upperBound
        else
            midPoint

    recurse 0 (Array.length toSearch - 1)

That works if the value we are searching for is in the array. If it's not, We'll end up with some funky endless recursion when the lower and upper bound cross over. Let's fix that, returning an int option instead of an int

let binarySearch (value: 'a) (toSearch: 'a array) =
    let rec recurse lowerBound upperBound =
        if lowerBound > upperBound then
            None
        else
            let midPoint = (upperBound + lowerBound) / 2
            let midValue = toSearch[midPoint]

            if midValue > value then
                recurse lowerBound (midPoint - 1)
            else if midValue < value then
                recurse (midPoint + 1) upperBound
            else
                Some midPoint

    recurse 0 (Array.length toSearch - 1)

And there you have it! Fully functional binary search in F#. Alhough you'll probably never have to implement a basic algorithm like this in F#, doing so is a fun way to improve your programming skills.