How Array#bsearch works in Ruby

Problem

Last time, I faced a problem with a algorithm test at hackerank.com (you might want to try it here), where I easily passed all normal testcases but not the performance ones.

Here is my first implementation:

# Complete the climbingLeaderboard function below.
def climbingLeaderboard(scores, alice)
    uniq_scores = scores.uniq
    alice.map do |alice_score|
        (uniq_scores.find_index{|score| alice_score >= score} || uniq_scores.length) + 1

    end
end

It seemed pretty simple at the first glance, and I had no idea why I failed 4/11 testcases due to time limit again and again.

After a while of researching (and getting a little grimace on my face lol), I finally found the reason. For a huge and sorted array, Array#find_index might wasn't a good idea where the satisfied result maybe located at the end of array. In this case better use Array#bsearch which an implementation of binary search algorithm.

I found this method very powerful and useful in so many case, so today I wanna show will you how this method works.

Array#bsearch introduction

As the doc mentions

bsearch {|x| block } → elem
You can use this method in two modes: a find-minimum mode and a find-any mode. In either case, the elements of the array must be monotone (or sorted) with respect to the block.

So depends on the passed block, there are 2 modes here:

• if the given block returns true/false value → find-minimum mode
• if the given block return integer number → find-any mode

Let's dive deeply into these 2 modes by examples !!

find-minimum mode

Example 1:

ary = [0, 4, 7, 10, 12]
ary.bsearch {|x| x >= 4 } #=> 4

Here x >= 4 is a block, and it returns true/false, so it's exactly the find-minimum mode. Let's break down step by step how this algorithm works in this case:

Remain array	Middle element (yield it to block)	Return value of block	Decision
[0, 4, 7, 10, 12]	7	7 >= 4 → true	Move to left side of array
[0, 4]	4	4 >= 4 → true	Move to left side of array
[0]	0	0 >= 4 → false	Move to right side of array → but there's no any element in the right of [0] → return last element which returned true which is 7

Example 2: Let's reverse the array, and see what happen

ary = [12, 10, 7, 4, 0]
ary.bsearch {|x| x >= 4 } #=> 12

Remain array	Middle element (yield it to block)	Return value of block	Decision
[12, 10, 7, 4, 0]	7	7 >= 4 → true	Move to left side of array
[12, 10]	10	10 >= 4 → true	Move to left side of array
[12]	12	12 >= 4 →	Move to left side of array → but there's no any element in the left of [12] → return last element which returned true which is 12

Hmm seems find-minimum will find the result that located in the lowest portion of array. Depends on the order of array, the result is also different, so we should be careful and choose appropriate block for each order of array.

Example 3:

ary = [0, 4, 7, 10, 12, 14]
ary.bsearch {|x| x == 4 } #=> nil
ary.reverse.bsearch {|x| x == 4 } #=> nil

@@ how could it be. Let's examine

Remain array	Middle element (yield it to block)	Return value of block	Decision
[0, 4, 7, 10, 12, 14]	10	10 == 4 → false	Move to right side of array
[12, 14]			Hmm it's gone to the wrong side of array, so it'll never find the result

Even we reverse the array

Remain array	Middle element (yield it to block)	Return value of block	Decision
[14, 12, 10, 7, 4, 0]	7	7 == 4 → false	Move to right side of array
[4, 0]	0	0 == 4 → false	Move to the right side of array
nil			So return the last element which returned true, in this case, there's no any → nil

Since this mode is not satisfy any more, let's try with find-any mode.

find-any mode

With this mode, each time param is yield to block, it will move to left of array, return, move to right of array if block returns negative number, 0, positive number respectively. More choices huh, let's try:

Example 4:

ary = [0, 4, 7, 10, 12, 14]
ary.bsearch {|x| x <=> 4 } #=> nil
ary.reverse.bsearch {|x| x <=> 4 } #=> 4

Remain array	Middle element (yield it to block)	Return value of block	Decision
[14, 12, 10, 7, 4, 0]	7	7 <=> 4 → 1	Move to right side of array
[4, 0]	0	0 <=> 4 → -1	Move to the left side of array
[4]	4	4 <=> 4 → 0	return 4

This one ary.bsearch {|x| x <=> 4 } #=> nil does not work because as I mentioned earlier in Example 2 it's not appropriate block for this array. To make things right, let's change:

ary.bsearch {|x| 4 <=> x } #=> 4

Example 5: Another example without spaceship <=> operator

ary = [0, 4, 7, 10, 12]
# Try to find v such that 4 <= v < 8
ary.bsearch { |x| 1 - x / 4 } #=> 7

Compared to the find-minimum mode, as its name, the find-any mode will stop right after found the satisfy element, not the leftmost or rightmost one as find-minimum mode.

Let's solve the problem with Array#bsearch

Since I want to find index of leftmost satisfy number → Let's use find-minimum mode:

def climbingLeaderboard(scores, alice)
    uniq_scores = scores.uniq
    alice.map do |alice_score|
        (uniq_scores.bsearch_index{ |score| alice_score >= score } || uniq_scores.length) + 1
    end
end

And the result:

Yayy!! Passed all testcases now

Summary

You've learned how to use bsearch in Ruby for searching an element in a monotone or sorted array. This can be useful in case you want to increasing performance and know exactly how array looks like.

Thanks for reading!

References

1. Wikipedia
2. Devdocs