arrow

ARROW-6093: [Java] reduce branches in algo for first match in VectorRangeSearcher

This is a follow up Jira for the improvement suggested by Francois Saint-Jacques in the PR for
https://github.com/apache/arrow/pull/4925

After careful analysis and proof, I found @fsaintjacques 's proposal really works. The idea behind the algorithm is tricky. This PR is the implementation based on @fsaintjacques 's proposal.

The benefit of this implementation:
1. the code is much clearer
2. there is fewer branches, which is beneficial for performance.

The drawback of this implementation:
1. there can be dumb iterations of the main loop. That is, the while loop may run a few more times after the "solution" is found, just to wait for the loop termination condition is satisfied.

However, the time complexity of the algorithm is still O(logn), and the number of dumb iterations can not be large.

Closes #5011 from liyafan82/fly_0805_range and squashes the following commits:

f47a2e7d8 <liyafan82>  reduce branches in algo for first match in VectorRangeSearcher

Authored-by: liyafan82 <fan_li_ya@foxmail.com>
Signed-off-by: Micah Kornfield <emkornfield@gmail.com>