h1. Binary Search for Ruby's Arrays

One incredibly handy algorithm that is missing from Ruby's Array class is the binary search.  If we *know* for *absolute certain* that the array we're working with is sorted you can use a binary search to search through the array much much more quickly than a linear search, which would be performed with index or detect/find.

Need proof?  Howsabout some benchmarks:

<pre>
== Benchmark Ruby's builtin :index method vs. a pure Ruby binary search method

Benchmark for 2000000 iterations searching through an array of 5 elements.
                  user     system      total        real
Index:        1.320000   0.010000   1.330000 (  1.320691)
Ruby BI:      8.700000   0.010000   8.710000 (  8.774825)

Benchmark for 1000000 iterations searching through an array of 10 elements.
                  user     system      total        real
Index:        0.990000   0.000000   0.990000 (  0.996690)
Ruby BI:      6.000000   0.010000   6.010000 (  6.043375)

Benchmark for 1000000 iterations searching through an array of 100 elements.
                  user     system      total        real
Index:        6.050000   0.020000   6.070000 (  6.091887)
Ruby BI:     10.250000   0.010000  10.260000 ( 10.318961)

Benchmark for 100000 iterations searching through an array of 1000 elements.
                  user     system      total        real
Index:        6.120000   0.010000   6.130000 (  6.155703)
Ruby BI:      1.480000   0.010000   1.490000 (  1.493227)

Benchmark for 10000 iterations searching through an array of 10000 elements.
                  user     system      total        real
Index:        5.880000   0.010000   5.890000 (  5.916098)
Ruby BI:      0.200000   0.000000   0.200000 (  0.206104)

Benchmark for 1000 iterations searching through an array of 100000 elements.
                  user     system      total        real
Index:        5.950000   0.010000   5.960000 (  6.005916)
Ruby BI:      0.030000   0.000000   0.030000 (  0.027823)



== Benchmark Ruby's builtin :index method vs. a native binary search method

Benchmark for 2000000 iterations searching through an array of 5 elements.
                  user     system      total        real
Index:        1.360000   0.000000   1.360000 (  1.369248)
Native BI:    1.140000   0.010000   1.150000 (  1.144739)

Benchmark for 1000000 iterations searching through an array of 10 elements.
                  user     system      total        real
Index:        0.960000   0.000000   0.960000 (  0.971568)
Native BI:    0.630000   0.000000   0.630000 (  0.637069)

Benchmark for 1000000 iterations searching through an array of 100 elements.
                  user     system      total        real
Index:        6.150000   0.010000   6.160000 (  6.192804)
Native BI:    0.810000   0.000000   0.810000 (  0.816337)

Benchmark for 100000 iterations searching through an array of 1000 elements.
                  user     system      total        real
Index:        6.170000   0.020000   6.190000 (  6.216637)
Native BI:    0.110000   0.000000   0.110000 (  0.111025)

Benchmark for 10000 iterations searching through an array of 10000 elements.
                  user     system      total        real
Index:        5.980000   0.010000   5.990000 (  6.033161)
Native BI:    0.010000   0.000000   0.010000 (  0.013183)

Benchmark for 1000 iterations searching through an array of 100000 elements.
                  user     system      total        real
Index:        5.920000   0.020000   5.940000 (  5.972206)
Native BI:    0.000000   0.000000   0.000000 (  0.001602)
</pre>

So, your array must be fairly large (between 100 and 1000 elements) for the Ruby version of binary_index to be faster than Ruby's builtin index method.  However, even for arrays as small as 5 elements, the native version of the binary_index method is faster than Ruby's index.  However, for very large sized Arrays, both the the pure and the native version are much much much faster than the builtin method.

<pre>
  <code>
    require 'binary_search/native'

    x = [5,1,6,7,2,6,4,2,6,1,6,1,1,8,3,5,2].sort
    puts x.binary_index(5)
  </code>
</pre>

So the actual method is 'binary_index' as it does the same thing that 'index' does: returns the index of a matching element.  It should be noted that 'index' returns the *first* instance of a matching element.  'binary_index' is not guaranteed to return the first.  It should also be noted, again, that this will only work if the array is sorted correctly.  If it's not weird crap will happen.

Oh yeah, and don't bother trying to require 'binary_search', it'll just throw an error telling you to either require 'binary_search/pure' or 'binary_search/native'.  I'd always use native... but some people are weird.