Hi, my name is Anatoli, I'm a Software Engineer from Berlin. During the day I work in Growth Team @ Blinkist. During the night I'm an Indie Maker of SQL Habit – online course that teaches data and SQL for Product and Marketing from 0 to Advanced.

Binary search with Ruby and TDD

If you have sorted array than you can search elements there easily with binary search. An interesting fact about binary search: only 10% of students are able to implement it correctly.

How does it work? Since the array is sorted (from lowest to highest) on each step we can split array in two parts and than compare middle element with element we are looking for – returning element if they coincide and calling binary search for particular half (right if mid is lower than required element and left is not).

So lets do some #TDD here and have some fun with that. When implementing binary search we should test if for empty array, array that doesn’t contains required element and some more cases. And pay attention to self.it method that introduces some sugar to write test cases.

require 'test/unit'

class TestArrayBindex < Test::Unit::TestCase
  def self.it name, &block
    define_method("test_#{name.gsub(/\W/,'_')}", &block) if block

  it 'should give same results as Array#index' do
    array = (1..100).to_a

    1.upto 100 do |i|
      assert_same array.bindex(i), array.index(i)

  it 'should return nil for empty array' do
    assert_same [].bindex(3), nil

  it 'should return 0 for array with 1 element' do
    assert_same [3].bindex(3), 0

  it 'should return right index for array with 2 elements' do
    array = [1, 2]
    assert_same array.bindex(1), 0
    assert_same array.bindex(2), 1

  it 'should return nil if there is no such element in array' do
    array = (1..100).to_a
    array.delete 75

    assert_same array.bindex(0), nil
    assert_same array.bindex(101), nil
    assert_same array.bindex(75), nil

You can simply copy this snippet and run it. You should have 5 failing tests as expected. It’s time to implement our Array#bindex method.

class Array
  def bindex element, lower = 0, upper = length - 1
    return if lower > upper
    mid = (lower + upper) / 2
    element < self[mid] ? upper = mid - 1 : lower = mid + 1
    element == self[mid] ? mid : bindex(element, lower, upper)

As you can see it is recursive implementation of the algorithm. And thanks to TDD now we can implement it in iterative manner. But before we start working on it lets do some benchmarking. Ruby provides two methods for finding index of an element: Array#index and Array#rindex. To get right benchmarking we should first take a look at sources of these methods. Index method simply iterates through the array and on each step compare element with required. Rindex does the same thing but it starts from the end and iterates to the beginning of the array. So because of it we will make two calls for it test – from the left part of the array and from the right:

require 'benchmark/ips'
Benchmark.ips do |r|
  array = (1..100).to_a

  r.report 'binary' do
    array.bindex 25
    array.bindex 75

  r.report 'rindex' do
    array.rindex 25
    array.rindex 75

  r.report 'index' do
    array.index 25
    array.index 75

# binary   624616.9 (±2.5%) i/s -    3135735 in   5.023492s
# rindex   241546.2 (±2.7%) i/s -    1218294 in   5.047591s
#  index   251110.4 (±2.7%) i/s -    1262720 in   5.032348s

As you can see rindex and index works with the same speed but binary search more than twice faster because it doesn’t look at every element. OK, so lets now implement iterative version of binary search and run at versus test we have.

class Array
  def iterative_bindex element, lower = 0, upper = length - 1
    while upper >= lower
      mid = (upper + lower) / 2
      if self[mid] < element
        lower = mid + 1
      elsif self[mid] > element
        upper = mid - 1
        return mid

    return nil

And of course we should benchmark all method together! We need just add one more block to benchmark:

r.report 'iterative bindex' do
  array.iterative_bindex 25
  array.iterative_bindex 75

#           binary   627299.2 (±2.3%) i/s -    3159927 in   5.040178s
#           rindex   243698.5 (±2.6%) i/s -    1229886 in   5.050344s
#            index   253722.6 (±2.1%) i/s -    1274260 in   5.024520s
# iterative bindex   831047.1 (±2.8%) i/s -    4182057 in   5.036514s

Seems like iterative version is the coolest :)

Full example source code

Are you full-stack developer or web designer? Join me at Growth Dev team at Blinkist!
I work in Growth Development team at Blinkist (app that allows you to read/listen short versions of non-fiction books), we maintain our webapps, design & ship AB-tests, build API integrations, analyse user data to improve our web products for millions of users. If you’re Rails developer with a passion for front-end or a web designer with a passion for growth – send me an email or ping on Twitter.
comments powered by Disqus