[Back to basics] Binary search

I decided to refresh my memory on basic data structures and algorithms. As an additional fun challenge, I decided to try and implement them in different programming languages/style.

Let’s give a good old binary search a go. The simplest of them all.

The algorithm

Binary search is a fast way of finding values in a sorted array.

It works very similarly to a person looking for a word in a dictionary (you know, from a bookshelf). Try imagining yourself searching for the word “help”.

In essence, it works like this:

1. Compare the value you look for with the element at the middle
2. If the element is less than the value you are looking for, continue searching the right side. Otherwise, the left side.
3. Repeat

You can read a bit more, for example, on Wikipedia

Performance

Because on each iteration we divide the array in two, the complexity is

O(log2(N))

How fast is that?

• For 1024 elements the algorithm makes ~10 iterations
• For 2048 elements it makes ~11 iterations
• For 4096 elements it makes ~12 iterations
• For 1.048.576 elements it makes only ~20 iterations.

As you can see, it scales incredibly good.

Ruby

Classic implementation

This is what I would anticipate seeing in books. Just a simple and efficient imperative solution.

Recursive implementation

Same as the previous one but instead of a loop recursion is used.

Compared to the classic implementation, it looks and a bit more expressive: instead of saying “move left/right limit” we say “search the value between those”. The problem here is that ruby doesn’t have tail-call optimisation. However, the amount of iterations is so low (<20 for 1000000 elements), it’s not really a problem.

Object-oriented (kind of) implementation

An immutable data structure representing a part of an array. The same as the recursive implementation but with an object wrapper.

The interesting bit about it is although it works exactly the same as the recursive version, it replaces the concept of left and right limits with a “slice” or we could even call it a “half”. The limits are encapsulated in the ArraySlice

Code golf

My attempt of writing a short solution.

• Using lambda reduces the number of symbols used for methods’ def ... end
• The formula for the middle index was shortened:
  x + (y — x) / 2 = (x + y) / 2
• Ternary operator and && were used instead of if.
• return was replaced with next , since it’s shorter

OCaml

OCaml version is quite straightforward. Since we can’t use null-value here, we need to use either Maybe or introduce our own type (which is what I did).

As far as I understand, it’s a common practice to introduce a nested auxiliary function for looping. This way we can provide a more meaningful interface to an API user (why would they care about left and right?)

Clojure

I noted two things about my Clojure solution:

1. Instead of using a helper function, as we did in OCaml, we can use loop which provides bindings for tail-recursion. In short, we can have our cake and eat it too :)
2. Clojure has immutable data structures and they are optimised. ArraySlice instances share the same array; we couldn’t slice it via array[0..mid] because it would create a new array every time, which would kill the performance. Clojure doesn’t have this “weakness”, we can slice arrays all we want, it won’t consume additional memory or processor’s time.

Conclusion

You can find the source code with some primitive tests (I didn’t put any effort in testing, just wanted to know if the implementation seems to work 😃) on Github.

Binary search is one of my most favourite algorithms. It’s simple and easy to implement; humans already use it themselves to some extent; it’s incredibly efficient (most of the algorithms I like are not the most efficient in their area).

Another important point is that knowing binary search is practical. Many people say that knowing classical algorithms and data structures is not really practical because you won’t use it in your everyday job (every standard library has sorting and basic data structures included). Binary search is a different thing.

Because it requires a sorted data in order for it to work, you usually won’t find it in standard libraries (I don’t think so, at least). However, you may face a situation when you work with an ordered piece of data and binary search may shine there. Also, its usefulness doesn’t end at computer programs. You may use it in the most unexpected real-life situations. Just look around you