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 1completed (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 foundcompleted (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 3completed (Y|n):   Handles more than trivial sized data set      - detail: consider a data set of the first 10000 integers      - example: Searching for 899 returns 898completed (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 2completed (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 elementcompleted (Y|n):   Supports sorted array of strings      - detail: Use [a, b, c, d] as the data set      - example: Searching for c returns 2completed (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 3completed (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 elementcompleted (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 endAnd, 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
BinarySearch Kata in Ruby
ruby;binary search;rspec