12 August 2013

Algorithmathon

On day 15 we will be looking into the Binary Search. It is a relatively straight forward algorithm for searching ordered data. Its a simple process where you pick an arbitrary location to start. You compare the value you are searching for with the value from the location selected. If the search value is higher you pick a value to the right for the next search. The search value might be lower in which case you would pick a value to the left. The key is to track the highest and lowest known value locations and to pick the middle location between them. This would work something like the following.

1. The first value and the last value are the low and high locations.

2. Pick the value in the middle of the the high and low values. Call this current value.

3. If the high and low values are equal then return nothing.

4. If the high location is greater than the number of values return nothing

5. If the low location is less than the first value location return nothing

6. If the search value is less than the current value make the current value location the high location and go to step 2.

7. If the search value is greater than the current value make the current location the low location and go to step 2.

8. Return the value location

As always we begin with our RSpec tests.

algorithm_array_spec.rb
require 'spec_helper'

describe AlgorithmArray do

describe "Class" do
it "should have method 'new_find'" do
AlgorithmArray.method_defined?(:new_find).should be_true
end
end

describe "Instance" do

describe "Start search from default location" do
before(:each) do
@array = AlgorithmArray.[](1,3,7,11,13,17,19,23,29,31)
end

it "should return 2 when 'new_find(7)' is called" do
@array.new_find(7).should == 2
end

it "should return 0 when 'new_find(1)' is called" do
@array.new_find(1).should == 0
end

it "should return 8 when 'new_find(29)' is called" do
@array.new_find(29).should == 8
end

it "should return 4 when 'new_find(13)' is called" do
@array.new_find(13).should == 4
end

it "should return nil when 'new_find(443)' is called" do
@array.new_find(443).should be_nil
end
end

describe "Start search from end location" do
before(:each) do
@array = AlgorithmArray.[](1,3,7,11,13,17,19,23,29,31)
end

it "should return 2 when 'new_find(7,9)' is called" do
@array.new_find(7,9).should == 2
end

it "should return 0 when 'new_find(1,9)' is called" do
@array.new_find(1,9).should == 0
end

it "should return 8 when 'new_find(29,9)' is called" do
@array.new_find(29,9).should == 8
end

it "should return 4 when 'new_find(13,9)' is called" do
@array.new_find(13,9).should == 4
end
end

describe "Start search from first location" do
before(:each) do
@array = AlgorithmArray.[](1,3,7,11,13,17,19,23,29,31)
end

it "should return 2 when 'new_find(7,0)' is called" do
@array.new_find(7,0).should == 2
end

it "should return 0 when 'new_find(1,0)' is called" do
@array.new_find(1,0).should == 0
end

it "should return 8 when 'new_find(29,0)' is called" do
@array.new_find(29,0).should == 8
end

it "should return 4 when 'new_find(13,0)' is called" do
@array.new_find(13,0).should == 4
end
end
end

end

And the code to satisfy these tests.

algorithm_array_spec.rb
class AlgorithmArray < Array
#Find the location of the matching element in the array.
#
#* *Args*    :
#+search_object+:: The object being looked for.
#* *Returns* :
#  - an integer representing the location in the array the matching element is located.
def new_find(search_object,start_location=nil)
if start_location.nil?
start_location=self.length/2
end
new_find_by_recursion(search_object,start_location,self.length-1,0)
end

private

#Find the location of the matching element in the array.
#
#* *Args*    :
#+search_object+:: The object being looked for.
#+search_location+:: The location in the array to compare values.
#+high+:: Tracks the lowest location in the array that is know to contain a value greater than the search_object.
#+high+:: Tracks the highest location in the array that is know to contain a value less than the search_object.
#* *Returns* :
#  - an integer representing the location in the array the matching element is located or nil if it is not found.
def new_find_by_recursion(search_object,search_location,high,low)
if search_location >= self.length || search_location < 0 || high == low
return
end
if self[search_location] < search_object
low = search_location
next_location = high - ((high - low)/2)
new_find_by_recursion(search_object,next_location,high,low)
elsif self[search_location] > search_object
high = search_location
next_location = low + ((high - low)/2)
new_find_by_recursion(search_object,next_location,high,low)
else
return_value = search_location
end
end

end

Less Is More ~ Older posts are available in the archive.