1#http://codekata.com/kata/kata02-karate-chop/
 2require "spec_helper"
 3
 4# Write a binary chop method that takes an integer search target and a sorted array of integers.
 5# It should return the integer index of the target in the array, or -1 if the target is not in the array.
 6# The signature will logically be:
 7
 8=begin
 9chop(int, array_of_int)  -> int
10=end
11
12# You can assume that the array has less than 100,000 elements.
13# For the purposes of this Kata, time and memory performance are not issues (assuming the chop terminates before you get bored and kill it, and that you have enough RAM to run it).
14
15
16describe "chop" do
17  def chop(int, items, r = 0)
18    return -1 if items.empty?
19    return items[0] == int ? r : -1 if items.length == 1
20
21    mid = items.length / 2
22    value = items[mid]
23
24    return r + mid if int == value
25
26    if int > value
27      chop(int, items[mid..items.length], mid)
28    else
29      chop(int, items[0..mid-1])
30    end
31  end
32
33  def chop(target, items)
34    low = 0
35    high = items.size
36
37    while low < high
38      mid = low + (high-low)/2
39      if items[mid] == target
40        return mid
41      elsif target > items[mid]
42        low = mid + 1
43      else
44        high = mid
45      end
46    end
47    -1
48  end
49
50  def assert_equal(expected, actual)
51    expect(actual).to eql(expected)
52  end
53
54  it 'chops' do
55    assert_equal(-1, chop(3, []))
56    assert_equal(-1, chop(3, [1]))
57    assert_equal(0,  chop(1, [1]))
58    #
59    assert_equal(0,  chop(1, [1, 3, 5]))
60    assert_equal(1,  chop(3, [1, 3, 5]))
61    assert_equal(2,  chop(5, [1, 3, 5]))
62    assert_equal(-1, chop(0, [1, 3, 5]))
63    assert_equal(-1, chop(2, [1, 3, 5]))
64    assert_equal(-1, chop(4, [1, 3, 5]))
65    assert_equal(-1, chop(6, [1, 3, 5]))
66    #
67    assert_equal(0,  chop(1, [1, 3, 5, 7]))
68    assert_equal(1,  chop(3, [1, 3, 5, 7]))
69    assert_equal(2,  chop(5, [1, 3, 5, 7]))
70    assert_equal(3,  chop(7, [1, 3, 5, 7]))
71    assert_equal(-1, chop(0, [1, 3, 5, 7]))
72    assert_equal(-1, chop(2, [1, 3, 5, 7]))
73    assert_equal(-1, chop(4, [1, 3, 5, 7]))
74    assert_equal(-1, chop(6, [1, 3, 5, 7]))
75    assert_equal(-1, chop(8, [1, 3, 5, 7]))
76  end
77end