Brian Douglas

Back to comp-sci 101, as I'm currently re-exploring the fundamentals of programming. As others choose to hand over their hard earned programming skills to the LLM I've decided to double down. So let's take a look at the binary search algorithm.

What is it?

It's a search algorithm.. Duh!

Binary search is an O(log n) search algorithm. This means that in the worst case scenario it will take as many steps as needed to get to the matching logarithmic value of 2. With a logarithim being the exponent by which a fixed value must be raised to produce the number in question. In other words 2 log 4 is 16 because 2 x 2 x 2 x 2 is 16.

Make sense? I hope so.

With this in mind by using binary search to search an array of 100 numbers it will only need to take 7 steps as 100 fits into 2 log 7. This is opposed to a simple search potentially having to check each number in the array O(n) to find the correct result. In other words we are measuring from the worst case scenario.

When we get to giant numbers this comes in handy as if we had a list of a billion numbers binary search would only have to check at most 32 numbers. As opposed to simple search potentially checking the full billion numbers.

The draw back of binary search however is that the list needs to be sorted. There may be overhead in the sorting, but once sorted the time saved searching should make up for that overhead.

How does it work?

It works by finding the mid point in a sorted array of numbers and checking if the number we are looking for is greater than or less than that mid point. If it is we can exclude half the numbers that we know are too large or too small. Each check halfs the size of the array till we are left with one item, the correct result. If the list does not contain the number we are searching for some null value, or -1 can be returned.

The code

Below is a version of binary search in Lua. Why lua? I just like Lua. And also it's not zero indexed, so that makes it quirky.

The below function takes an array of numbers to search, the haystack, and attempts to find the index of a certain number, the needle. I really like the haystack/needle analogy. It makes a lot of conceptual sense to me.

Lua has now len method to get the size of an array, a table in Lua. Instead it has a len operator #. So to get the number of items in a table we use len = #table

function binary_search(haystack, needle)
    low = 1
    high = #haystack

    while low <= high do
        mid = math.floor((low + high) / 2)
        check = haystack[mid]

        if check == needle then
            return mid
        elseif check > needle then
            high = mid - 1
        else
            low = mid + 1
        end
    end

    return -1
end

assert binary_search({1, 3, 5, 7, 9}, 5)  ==  3
assert binary_search({1, 3, 5, 7, 9}, 12) == -1
assert binary_search({1, 3, 5, 7, 9}, 9)  ==  5