Algorithms

binary_search.rb

def solution(x, array)
  min   = 0
  max   = array.size - 1
  index = -1

  begin
    # avg = (min + max) / 2
    # avg = min + (max - min) / 2
    # avg = min + (max - min) >> 1
    avg = (min & max) + ((min ^ max) >> 1)
    case array[avg] <=> x
    when -1 then min = avg
    when 0  then return index = avg
    when 1  then max = avg
    end
  end while 0 < avg && avg < array.size

  index
end

require 'minitest/autorun'
require 'benchmark'

class Tests < MiniTest::Test
  def test_example_input
    assert_equal 1, solution(2, [1, 2, 3, 4, 5, 6])
    assert_equal -1, solution(2, [1, 3, 4])
    assert_equal 5, solution(72, [20, 23, 31, 42, 57, 72, 88])
    assert_equal 0, solution(1, [1, 123, 230, 99999])
    assert_equal 0, solution(1, [1])
    assert_equal 0, solution(1, (1..2**25).to_a) # 25 operations => log(2**25) == 25
  end
end

# avg = (min + max) / 2 # (usual)
#
# real    0m1.238s
# user    0m1.140s
# sys     0m0.080s
#
# avg = min + (max - min) / 2 # (faster)
#
# real    0m1.142s
# user    0m1.020s
# sys     0m0.110s
#
# avg = min + (max - min) >> 1 # (fastest with overflow issues)
#
# real    0m1.110s
# user    0m0.980s
# sys     0m0.120s
#
# avg = (min & max) + ((min ^ max) >> 1) # (fastest without overflow issues)
#
# real    0m1.096s
# user    0m0.980s
# sys     0m0.100s