BinarySearch Kata in Ruby

Question

I've just completed this binary search kata - which has some weird requirements - and I spent a little while "cleaning" up my code and making it more compact. I would appreciate some feedback on the readability of the BinarySearch class. I've packed a lot of logic into some of the lines and I'd like to know if that makes it more or less readable.

A Ruby Kata for Binary Search of Arrays:

Binary Search Kata
   Create a binary search class that is initialized with an array of integers
      - detail: Do not use built in array functions
      - detail: The initial array is [1,3]
      - detail: return the index of the search value if found
      - example: searching for 3 returns 1

completed (Y|n):

   Successfully deal with values that are not in the data set
      - example: searching for 5 indicates to the caller the value is not found

completed (Y|n):

   Binary Search handles an odd number of elements in the data set
      - detail: Allows the data set to be redefined with [1,3,5,7,9]
      - example: Searching for 5 returns 2
      - example: Searching for 7 returns 3

completed (Y|n):

   Handles more than trivial sized data set
      - detail: consider a data set of the first 10000 integers
      - example: Searching for 899 returns 898

completed (Y|n):

   Supports duplicate elements in the data set
      - detail: Use [1,3,5,5,7,9] as the data set
      - example: Searching for 3 returns 1
      - example: Searching for 5 returns 2

completed (Y|n):

   Handles expired call for duplicate elements
      - detail: Use [1,3,5,5,7,9] as the data set
      - example: Third call to search for 5 is handled like missing element

completed (Y|n):

   Supports sorted array of strings
      - detail: Use ["a", "b", "c", "d"] as the data set
      - example: Searching for "c" returns 2

completed (Y|n):

   Supports duplicate strings
      - detail: Use ["a", "b", "c", "c", "d"] as the data set
      - example: First search for "c" returns 2
      - example: Second search for "c" returns 3

completed (Y|n):

   Handles expired call for duplicate string elements
      - detail: Use ["a", "b", "c", "c", "d"] as the data set
      - example: Third call to search for "c" is handled like missing element

completed (Y|n):

┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━┓
┃ Requirement                                                                      ┃ Time     ┃
┣━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╊━━━━━━━━━━┫
┃ Create a binary search class that is initialized with an array of integers       ┃ 00:04:02 ┃
┣━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╊━━━━━━━━━━┫
┃ Successfully deal with values that are not in the data set                       ┃ 00:04:09 ┃
┣━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╊━━━━━━━━━━┫
┃ Binary Search handles an odd number of elements in the data set                  ┃ 00:10:49 ┃
┣━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╊━━━━━━━━━━┫
┃ Handles more than trivial sized data set                                         ┃ 00:02:28 ┃
┣━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╊━━━━━━━━━━┫
┃ Supports duplicate elements in the data set                                      ┃ 00:05:17 ┃
┣━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╊━━━━━━━━━━┫
┃ Handles expired call for duplicate elements                                      ┃ 00:10:35 ┃
┣━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╊━━━━━━━━━━┫
┃ Supports sorted array of strings                                                 ┃ 00:02:27 ┃
┣━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╊━━━━━━━━━━┫
┃ Supports duplicate strings                                                       ┃ 00:02:35 ┃
┣━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╊━━━━━━━━━━┫
┃ Handles expired call for duplicate string elements                               ┃ 00:00:57 ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┻━━━━━━━━━━┛

Questions:
   - What about supporting duplicate data changed your solution?
   - Did your approach get better or worse after dealing with duplicates?
   - What was the hardest part about adding support for strings?
   - Can you think of a different technique for building the kata?
   - What can you say about the relative merits of the various techniques you chose?
   - Which is the most likely to make it into production code?
   - Which was the most fun to write?
   - Which requirement was the hardest to get working?
   - For all of the above, ask yourself why?

My Specs:

  1 require 'spec_helper'
  2 require 'binary_search'
  3 require 'its'
  4
  5 describe BinarySearch do
  6   subject(:binary_search) { BinarySearch.new(data) }
  7   let(:data) { [1,3] }
  8
  9   describe "#initialize" do
 10     it "instantiates" do
 11       expect { binary_search }.to_not raise_exception
 12     end
 13   end
 14
 15   describe '.find' do
 16     its(:find, 3) { should eq(1) }
 17     its(:find, 5) { should be_nil }
 18
 19     context 'odd numbers of elements in data set' do
 20       let(:data) { [1,3,5,7,9] }
 21       its(:find, 0) { should be_nil }
 22       its(:find, 1) { should eq(0) }
 23       its(:find, 2) { should be_nil }
 24       its(:find, 3) { should eq(1) }
 25       its(:find, 4) { should be_nil }
 26       its(:find, 5) { should eq(2) }
 27       its(:find, 6) { should be_nil }
 28       its(:find, 7) { should eq(3) }
 29       its(:find, 8) { should be_nil }
 30       its(:find, 9) { should eq(4) }
 31       its(:find, 10) { should be_nil }
 32     end
 33
 34     context 'non trivial data sets' do
 35       let(:data) { [] }
 36       before { for i in 1..10000 do data << i end }
 37       its(:find, 899) { should eq(898) }
 38     end
 39
 40     context 'duplicate data elements' do
 41       let(:data) { [1,3,5,5,7,9] }
 42       its(:find, 3) { should eq(1) }
 43       its(:find, 5) { should eq(2) }
 44       it 'handles expired calls for duplicate elements' do
 45         2.times do binary_search.find(5) end
 46         binary_search.find(5).should be_nil
 47       end
 48     end
 49
 50     context 'sorted array of strings' do
 51       let(:data) { ['a','b','c','d'] }
 52       its(:find, 'a') { should eq(0) }
 53       its(:find, 'b') { should eq(1) }
 54       its(:find, 'c') { should eq(2) }
 55       its(:find, 'd') { should eq(3) }
 56       its(:find, 'x') { should be_nil }
 57     end
 58
 59     context 'duplicate strings' do
 60       let(:data) { ['a', 'b', 'c', 'c', 'd'] }
 61       its(:find, 'c') { should eq(2) }
 62       it 'handles multiple searches' do
 63         binary_search.find('c')
 64         binary_search.find('c').should eq(3)
 65       end
 66       it 'handles expired calls for strings' do
 67         2.times do binary_search.find('c') end
 68         binary_search.find('c').should be_nil
 69       end
 70     end
 71   end
 72 end

And, the BinarySearch Class:

  1 class BinarySearch
  2   def initialize(data)
  3     @data = data
  4     @search_hash = Hash.new
  5   end
  6
  7   def find(target)
  8     return @search_hash[target] = first_find(target) unless @search_hash[target]
  9     return @data[@search_hash[target] + 1] == target ? @search_hash[target] += 1 : nil
 10   end
 11
 12   private
 13
 14   def first_find(target)
 15     return nil unless pivot = bsearch(target, @data)
 16     pivot -= 1 while @data[pivot - 1] == target
 17     return pivot
 18   end
 19
 20   def bsearch(target, data)
 21     pivot = data.length / 2
 22
 23     return pivot if data[pivot] == target
 24     return nil if pivot == 0
 25
 26     if data[pivot] > target
 27       return bsearch(target, data[0..pivot - 1])
 28     else
 29       offset = bsearch(target, data[pivot..-1])
 30       return offset ? pivot + offset : nil
 31     end
 32   end
 33 end

Answer 1

This is pretty good code. It is a little compact, but that only hurts readability in a few places. I will make some suggestions that fluff it out just a bit, and might make it more understandable for some readers. Most of what I bring up here is quite minor. The important stuff is at the end, where I suggest reorganizing #find, and describe a bug.

Prefer {...} for single-line blocks

{...} is preferred for single-line blocks; begin...end for multi-line. So, instead of this:

2.times do binary_search.find('c') end

this:

2.times { binary_search.find(5) }

Implicit vs. explicit return

The value of the last executed expression in a method becomes the return value of the method; this allows you to omit many instances of return. So, instead of this:

  ...
  return pivot
end

you can do this:

  ...
  pivot
end

The value of an "if" expression is the value of the last expression it executed, so instead of this:

if data[pivot] > target
  return bsearch(target, data[0..pivot - 1])
else
  offset = bsearch(target, data[pivot..-1])
  return offset ? pivot + offset : nil
end

you can do this:

if data[pivot] > target
  bsearch(target, data[0..pivot - 1])
else
  offset = bsearch(target, data[pivot..-1])
  offset ? pivot + offset : nil
end

Typo in a "describe" description

I think this is just a typo. Since find is an instance method, this:

describe '.find' do

should instead be:

describe '#find' do

Testing that the constructor does not die

Since every one of the specs implicitly tests that the constructor does not die, and because that is the normal expectation for a constructor, there is no need to implicitly test that the constructor does not raise an exception. This can safely be removed from the spec:

describe "#initialize" do
  it "instantiates" do
    expect { binary_search }.to_not raise_exception
  end
end

Names

• In class BinarySearch, the instance variable @search_hash needs a better name. This one is a bit tough (naming is hard!), but until a truly good name is found, I suggest @found_indices as a name that gives the reader a better clue about what the hash is being used for.

• A better name for BinarySearch#find might be index. This is consistent with the built-in Array#index, and so less surprising.

• Similarly, consider renaming BinarySearch#first_find to first_index.

Creating a hash

It is more usual, when creating an empty hash, to do this:

@found_indices = {}

rather than this:

@found_indices = Hash.new

Use && to eliminate a use of the trinary operator

This:

offset ? pivot + offset : nil

may be more succinctly stated as:

offset && pivot + offset

Expanding BinarySearch#find

I had trouble following the flow of control here:

def find(target)
  return @search_hash[target] = first_find(target) unless @search_hash[target]
  return @data[@search_hash[target] + 1] == target ? @search_hash[target] += 1 : nil
end

We can make it easier to follow, and solve another problem: It isn't obvious at first that this binary search handles duplicate values by return successive indices. Let's draw it in crayon:

def find(target)
  unless @found_indices[target]
    find_first(target)
  else
    find_next(target)
  end
end

private

def find_first(target)
  @found_indices[target] = first_index(target)
end

def find_next(target)
  next_index = @found_indices[target] + 1
  return nil unless @data[next_index] == target
  @found_indices[target] = next_index
  next_index
end

The result of @found_indices[target] = next_index is next_index, so the last line that explicitly returns next_index is, strictly speaking, unnecessary. However, it does make the code more clear.

A bug with repeating values

If the array has only one distinct value, whether repeated or not, then there's a bug. This spec exposes it:

context 'array of identical values' do
  let(:data) { [1, 1] }
  specify do
    binary_search.find(1).should eq 0  # => Expected 0; got -2
    binary_search.find(1).should eq 1
    binary_search.find(1).should be_nil
  end
end

The problem is here:

def first_index(target)
  return nil unless pivot = bsearch(target, @data)
  pivot -= 1 while @data[pivot - 1] == target        # The bug is here
  pivot
end

When pivot is 0, the expression @data[pivot - 1] becomes @data[-1], which gets the last value in @data. The code ends up wrappting from the beginning to the end of the array. The fix is to check that pivot is greater than 0 before decrementing it:

  pivot -= 1 while pivot > 0 && @data[pivot - 1] == target