5
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ please, don't include line numbers in the code or you're forcing people to remove them... can you edit it? \$\endgroup\$ – tokland Mar 21 '14 at 16:27
  • \$\begingroup\$ Sorry about that. Line numbers are super easy to remove in vim so I never realized they were a pain for others. I'll edit the question when I'm back at my desk. Or, you can edit it for sweet smelling karma. Jamal follows me around deleting all of my "pleases" and "thank yous" to get those points. You could actually improve the question for your karma ;) \$\endgroup\$ – user341493 Mar 22 '14 at 1:59
  • \$\begingroup\$ What rspec extension, or what version of rspec, is providing the special syntax for its? \$\endgroup\$ – Wayne Conrad Mar 22 '14 at 2:44
  • \$\begingroup\$ That's the "its" gem. \$\endgroup\$ – user341493 Mar 22 '14 at 17:49
  • \$\begingroup\$ This is a good question. Would you consider replacing the section named "A Ruby Kata for Binary Search of Arrays" with a link to the Kata? That section didn't help me to understand the exercise, so it can probably go. A link to the kata, however, would be valuable. \$\endgroup\$ – Wayne Conrad Mar 23 '14 at 13:20
2
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.