Skip to content

Instantly share code, notes, and snippets.

@mowat27
Last active December 22, 2015 03:28
Show Gist options
  • Select an option

  • Save mowat27/6410267 to your computer and use it in GitHub Desktop.

Select an option

Save mowat27/6410267 to your computer and use it in GitHub Desktop.
Binary Chop kata
require 'rspec-given'
# Really, really, really going nowhere with this at the moment :-(
class Chop
def initialize(list)
@list = list
end
def find(item, start = 0)
mid_point = @list.length / 2
next_point = mid_point + 1
top = @list[next_point..-1]
bottom = @list[0...next_point]
return nil if top.nil? || bottom.empty?
if bottom.last == item
mid_point + start
else
Chop.new(top).find(item, next_point)
end
end
end
describe "binary chop" do
Then { Chop.new([99]).find(99) == 0 }
Then { Chop.new([98,99]).find(99) == 1 }
Then { Chop.new([97,98,99]).find(99) == 2 }
Then { Chop.new([97,98,99]).find(98) == 1 }
Then { Chop.new([97,98,99]).find(97) == 0 } # Failing at the moment
Then { Chop.new([97,98,99]).find(100).nil? }
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment