algorithm practice: bsearch

bsearch.rb

require 'pp'

def chop(key, a)
  low = 0
  high = a.size - 1
  while low < high do
    mid = (low + high) / 2
    val = a[mid]
    return mid if val == key
    if val > key
      high = mid - 1
    else
      low = mid + 1
    end
  end
  return low if a[low] == key
  -1
end

def assert_chop(exp, key, a)
  # pp [key, a]
  val = chop(key, a)
  if exp != val
    pp [a, key]
    puts val
    puts "Expected: #{exp}"
    raise 'error'
  end
end

def test_chop
  15.times do |n|
    a = Array.new(n) { |n| n }
    assert_chop(-1, -1, a)
    n.times do |i|
      assert_chop(i, i, a)
    end
  end
end

test_chop