This content originally appeared on DEV Community and was authored by Kevin Luo
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,
- The block you send to the
#bsearchmust return aBooleanvalue,falseortrue. - If we apply
Array.mapwith the same block, it should return a series offalsevalues followed by a series oftruevalues. -
#bsearchwill return the first element which returnstrue
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,
- The block you send to the
#bsearchmust return aNumericvalue - It returns a positive number if an array element is smaller than the values you're searching
- It returns a negative number if an array element is greater than the values you're searching
- 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 is0 - if
a > b, then the result is1
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!❤️
This content originally appeared on DEV Community and was authored by Kevin Luo
Kevin Luo | Sciencx (2025-02-24T01:46:23+00:00) How to do binary search for Ruby’s array by #bsearch. Retrieved from https://www.scien.cx/2025/02/24/how-to-do-binary-search-for-rubys-array-by-bsearch/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.