But my first couple of runs resulted in relatively long procedures with a lot of boundary checking. While my specs were passing, the smell of the code was really bothering me.
I found a reference implementation and gave it a run, but discovered that it failed my specs. After a double-check of the specs to confirm I didn't have something messed up, I decided to dump the RI and try it again.
Finally, the pieces fell together and I could see where most of the boundary checking fell out of the method as I changed the sequence of events.
class Chop def self.find(lookFor, lookIn, start_index=nil, end_index=nil) start_index ||= 0 end_index ||= lookIn.length middle = (start_index + end_index)/2 return middle if lookFor == lookIn[middle] return -1 if ((middle == start_index) || (middle == end_index)) return find(lookFor, lookIn, start_index, middle) if lookFor < lookIn[middle] return find(lookFor, lookIn, middle, end_index) if lookFor > lookIn[middle] end end
require "spec" require "karate_chop" describe Chop do context "with an empty sorted array" do it "indicates item not found" do Chop.find(1, ).should == -1 end end context "with search target not in array" do it "indicates item not found" do Chop.find(1, [0,2,3]).should == -1 end end context "with search target in array" do it "provides the index of the located item when in the middle of the array" do Chop.find(1, [0,1,2,3]).should == 1 Chop.find(4, [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21]).should == 4 end it "provides the index of the located item when it is last in the array" do Chop.find(20, [5, 10, 15, 20]).should == 3 end it "provides the index of the located item when it is first in the array" do Chop.find(20, [20,40,60,80]).should == 0 end end context "with a large array" do it "locates the item" do search_in = Array(0..900) Chop.find(100, search_in).should == 100 end end end
I am looking for feedback on these. Please, feel free to let me know how I could improve my code or specs. Or share links to your own solutions.