How Array#bsearch works in Ruby

# Problem
Last time, I faced a problem with a algorithm test at [hackerank.com](https://www.hackerrank.com/) (you might want to try it [here](https://www.hackerrank.com/challenges/climbing-the-leaderboard/problem?fbclid=IwAR3vgvsOpt5zIPynDIYYR-0AuMtf6EMewZhS6NrSk2ExeJb0ftTKj0P9NjY)), 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.
<img width="867" alt="Screen Shot 2019-12-08 at 11.26.05 AM.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/542870/62798105-ba2f-ffd3-1a97-549ceca13689.png">
 
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](https://apidock.com/ruby/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](https://devdocs.io/ruby~2.5/array#method-i-bsearch). 

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: 

```ruby
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
```ruby
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: 
```ruby
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:

```ruby
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

```ruby
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`:

```ruby
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:

![Screen Shot 2019-12-12 at 3.05.46 PM.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/542870/2c7b19b4-7a80-e6fc-2246-9cd6d1f35a29.png)

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](https://en.wikipedia.org/wiki/Binary_search_algorithm)
2. [Devdocs](https://devdocs.io/ruby~2.5/array#method-i-bsearch)