1つ目のちゃんと動く実装

test_chop.rb

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

require 'minitest/autorun'

def chop(target, values)
  min_index  = 0
  half_index = values.length / 2
  max_index  = values.length - 1

  while true
    #puts "min:#{min_index}, half:#{half_index}, max:#{max_index}"
    return half_index if values[half_index] == target
    return -1         if half_index <= min_index || max_index <= half_index

    if values[half_index] > target
      max_index  = half_index
      half_index = half_index / 2
    else
      min_index  = half_index
      half_index = (values.length + half_index) / 2
    end
  end

  -1
end

class TestChop < MiniTest::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

実行結果

[takatoshi@maui tmp]$ ruby -v
ruby 2.1.2p95 (2014-05-08 revision 45877) [x86_64-darwin13.0]
[takatoshi@maui tmp]$ ruby test_chop.rb 
MiniTest::Unit::TestCase is now Minitest::Test. From test_chop.rb:28:in `<main>'
Run options: --seed 58836

# Running:

.

Finished in 0.003046s, 328.2994 runs/s, 6237.6888 assertions/s.

1 runs, 19 assertions, 0 failures, 0 errors, 0 skips

Goals に書いてあることすっかり忘れてた

http://codekata.com/kata/kata02-karate-chop/

keep a note of the kinds of error you encounter

全然メモってない

思い出せるだけメモってみる

• 最初 values を本当に分割してしまっていた
  • そして分割後の index を return していた...
• values の左端と右端の index を管理するという方法を思いつくまで時間がかかった
• 本当に一番最初に書いたコードはひどすぎて思い出せない

  max_index  = half_index
  half_index = half_index / 2

この2行の順番を逆にしていてうまくいかなかった