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!