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. Thanks!
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
