Algorithmathon Day 15: Binary Search

Created: 12 August 2013  Modified:

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
tags: Algorithm - Algorithmathon - Binary Search - RSpec - Ruby
   Less Is More