BinarySearch Kata in Ruby

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:
- Did your approach get better or worse after dealing with duplicates?
- 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

• please, don't include line numbers in the code or you're forcing people to remove them... can you edit it? – tokland Mar 21 '14 at 16:27
• 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 ;) – user341493 Mar 22 '14 at 1:59
• What rspec extension, or what version of rspec, is providing the special syntax for its? – Wayne Conrad Mar 22 '14 at 2:44
• That's the "its" gem. – user341493 Mar 22 '14 at 17:49
• 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. – Wayne Conrad Mar 23 '14 at 13:20

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


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