test_chop.rb

#!/usr/bin/env ruby
# http://codekata.com/kata/kata02-karate-chop/

require 'test/unit'

def chop(target, values)
  index = values.index(target)
  index.nil? ? -1 : index
end

class TestChop < Test::Unit::TestCase
  def test_chop
    assert_equal(-1, chop(3, []))
    assert_equal(-1, chop(3, [1]))
    assert_equal(0,  chop(1, [1]))
    #
    assert_equal(0,  chop(1, [1, 3, 5]))
    assert_equal(1,  chop(3, [1, 3, 5]))
    assert_equal(2,  chop(5, [1, 3, 5]))
    assert_equal(-1, chop(0, [1, 3, 5]))
    assert_equal(-1, chop(2, [1, 3, 5]))
    assert_equal(-1, chop(4, [1, 3, 5]))
    assert_equal(-1, chop(6, [1, 3, 5]))
    #
    assert_equal(0,  chop(1, [1, 3, 5, 7]))
    assert_equal(1,  chop(3, [1, 3, 5, 7]))
    assert_equal(2,  chop(5, [1, 3, 5, 7]))
    assert_equal(3,  chop(7, [1, 3, 5, 7]))
    assert_equal(-1, chop(0, [1, 3, 5, 7]))
    assert_equal(-1, chop(2, [1, 3, 5, 7]))
    assert_equal(-1, chop(4, [1, 3, 5, 7]))
    assert_equal(-1, chop(6, [1, 3, 5, 7]))
    assert_equal(-1, chop(8, [1, 3, 5, 7]))
  end
end

ずるをした。問題は「バイナリサーチを実装しろ」だった
また Array#index は配列の要素を順番に見ているだけのようだった
https://github.com/ruby/ruby/blob/8e274670ec4b4704bb23f42860ed539ec3c990c3/array.c#L1449

あ、バイナリサーチではないのか・・・

• in the first pass it determines whether the required value is in the top or the bottom half of the list of values
  • 探している値が上半分と下半分のどちらにあるか決める
• In the second pass in considers only this half, again dividing it in to two
  • その半分をさらに半分にする
• It stops when it finds the value it is looking for, or when it runs out of array to search
  • 探している値が見つかるか、配列が空になったらやめる

やっぱりバイナリサーチだった

Array#bsearch というのがあった
http://ruby-doc.org/core-2.1.1/Array.html#method-i-bsearch