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