require 'rspec'

class Array
  def binary_search(value, index = 0)
    middle = self[size/2]
    if middle == value
      index + size/2
    elsif size == 1
      -1
    elsif middle < value
      self[(size/2 + 1)..-1].binary_search(value, index + size/2 + 1)
    else
      self[0..(size/2 - 1)].binary_search(value, index)
    end
  end
end

describe Array do
  describe "#binary_search" do
    let(:array) { %w(a b c d e f g h i j k l m n oh-hai p q r s t u v w x y z) }
    subject { array.binary_search(value) }

    context "not found" do
      let(:value) { 'not there' }

      it "returns -1" do
        should eq -1
      end
    end

    context "found" do
      context "middle" do
        let(:value) { 'n' }

        it 'returns the index' do
          should eq 13
        end
      end

      context "somewhere else" do
        let(:value) { 'oh-hai' }

        it "returns the index" do
          should eq 14
        end
      end
    end
  end
end