How to do binary search for Ruby's array by #bsearch

We sometimes need to check if a value is included in an array. There are many methods to achieve that, e.g. Array#include?, Array#find, etc. But they use linear search, which time complexity is O(n). If it's a sorted array, we know the binary search can give you O(logn) speed. It would be a shame if you didn't know that Ruby's Array can perform binary search out of the box by Array#bsearch. Unfortunately, it may not be that intuitive to use so many people don't know hot to use it. Let's see some examples first:

If you don't know what happened there, you can continue reading this article to know that 😉

There are two very important things to know when using Array#bsearch. First, it can only be performed on a sorted array. Array#bsearch doesn't sort the array for you (you can call array.sort first if you're not sure). Second, Array#bsearch has two modes. That means it has two different ways to use it. The first mode is called Find-Minimum mode, and the other one is called Find-Any mode. These two modes actually do a very similar thing, but you need to send two completely different blocks to it.

Find-Minimum mode

When using Find-Minimum mode,

1. The block you send to the #bsearch must return a Boolean value, false or true.
2. If we apply Array.map with the same block, it should return a series of false values followed by a series of true values.
3. #bsearch will return the first element which returns true

I believe it is easier to understand when seeing the real examples.

array = [1, 3, 5, 7, 9]
array.bsearch { |x| x >= 5 } # => 5

It returns 5, because 5 is the first element that makes the block { |x| x >= 5 } to return true:

# compute x >= 5 for all elements
# [1,     3,     5,    7,    9 ]
[false, false, true, true, true]

If we use another to another block { |x| x >= 6 }

array.bsearch { |x| x >= 6 } # => 7

It returns 7. Why? Again, it is because 7 is the first element make the block return true

# [1,     3,     5,     7,    9 ]
[false, false, false, true, true]

If I use the block { |x| x >= 10 },

array.bsearch { |x| x >= 10 } # => nil

Because there is no element in the array able to make the block return true, the nil will be returned.

Find-Any mode

When using Find-Any mode,

1. The block you send to the #bsearch must return a Numeric value
2. It returns a positive number if an array element is smaller than the values you're searching
3. It returns a negative number if an array element is greater than the values you're searching
4. It should return zero, if the element matches what you're searching

Even though the rules above feel much more complex than the Find-Minimum mode, trust me, it's also simple.

array = [1, 3, 5, 7, 9]
array.bsearch { |x| 5 <=> x } # => 5

What is <=>? This <=> is called a 3-way comparison, a.k.a spaceship operator. If we compare a <=> b

• if a < b, then the result is -1
• if a == b, then the result is 0
• if a > b, then the result is 1

If you really want to remember it, I hope the picture below can help you:

Anyway, coming back to our example, let's see the computed results of { |x| 5 <=> x } for each element:

array.map { |x| 5 <=> x }
# [1, 1, 0, -1, -1]

5 makes the block return 0, so 5 is returned. If I try to search 6

array.bsearch { |x| 6 <=> x } # => nil

It returns nil because the computed results of { |x| 6 <=> x } is

array.map { |x| 6 <=> x }
# [1, 1, 1, -1, -1]

and it doesn't have 0 in it.

Find-Any mode is very powerful. We can search for a range instead of a single element. For example,

array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
array.bsearch do |x|
  if x < 4
    1
  elsif x > 6
    -1
  else
    0
  end
end

because the block's results of the array is:

# [1, 2, 3, 4, 5, 6,  7,  8,  9, 10]
  [1, 1, 1, 0, 0, 0, -1, -1, -1, -1]

4, 5 and 6 make the block return 0, so array.bsearch will return any one of them as a result. That's why it is called Find-Any mode.

Conclusion

If you scroll to the top and check the first screenshot now, I think you can understand it. No matter which mode you use, the most important thing is that the search time is O(logn). If you have a very looooong sorted array to search, and Array.find feels so slow (which uses linear search), try Array#bsearch, you will love it!❤️