Binary Search

API

int ret = Arrays.binarySearch(Object[] source, int fromIndex, int toIndex, Object target).

其中 fromIndex為 lo, toIndex為 hi+1, 表示到toIndex為止但不包含toIndex本身, 使用時務必小心，若錯將toIndex當成hi輸入就會有錯。

或不指定範圍:

int ret = Arrays.binarySearch(Object[] source, Object target).

  int low = fromIndex;
  int high = toIndex - 1;

ret >= 0 , the index of the target, ex. source[ret] is equal to target

ret < 0, the target is not existed in source, however if we want to insert it to the current source, the position will be 從左邊數來第ret個的位置.

Arrays.binarySearch(new int[]{1,3,4,6}, 0, 4, 5) 
// return -4, 若插入5應該會是 1, 3, 4, 5, 6
// 5的位置在左邊數來第4個，所以回傳-4

Binary search是用來尋找在某個範圍中滿足條件的最小元素

Basic implementation code flow

While interation, we have to be aware of the changes of lo. It should base on mid with some edit. Please note that :

We can't set lo identical to mid after iteration. After all, the mid is calulated by \\int mid = lo + (hi-lo)/2; If lo is equal to previous mid, the the mid we got from this code will be equal to previous mid in some cases.

Let's say, [1,2], lo = 0, hi = 1, mid = (1-0)/2 = 0, so if we set lo = mid = 0, the next case will be lo = 0, hi = 1, it becomes a infinited loop.

Another way to explain this is that, if mid satisfied the condition, it implied that all the nodes from mid+1 to hi will satify this condition too. Our goal is to find out the smallest one in the array to fullfill this condition, so we should ingore the nodes among mid+1 to hi. Therefore the next interval should be lo to mid, where the current hi became the mid.

On the contrary, if mid is not satified the condition, which imply mid should not be in the next checking interval. as result of that, the interval should be mid+1 to hi.

int lo = 0, hi = arr.length;

while( lo < hi ){
    int mid = lo + (hi-lo)/2;
    if(condition(mid)){
        hi = mid;
    }else{
        lo = mid+1;
    }
}
if(!condition(left)) return -1; //Please note that it is possible can't find one
return left;

What's really nice of this template is that, for most of the binary search problems, we only need to modify three parts after copy-pasting this template, and never need to worry about corner cases and bugs in code any more:

• Correctly initialize the boundary variables left and right. Only one rule: set up the boundary to include all possible elements;

• Decide return value. Is it return left or return left - 1? Remember this: after exiting the while loop, left is the minimal k​ satisfying the condition function;

• Design the condition function. This is the most difficult and most beautiful part. Needs lots of practice.

Below I'll show you guys how to apply this powerful template to many LeetCode problems.

Advanced application

The above problems are quite easy to solve, because they already give us the array to be searched. We'd know that we should use binary search to solve them at first glance. However, more often are the situations where the search space and search target are not so readily available. Sometimes we won't even realize that the problem should be solved with binary search -- we might just turn to dynamic programming or DFS and get stuck for a very long time.

As for the question "When can we use binary search?", my answer is that, If we can discover some kind of monotonicity, for example, if condition(k) is True then condition(k + 1) is True, then we can consider binary search.

當某個值能使condition成立時，所有比這個值大的值都必能使condition成立。這種狀況就可以使用biniary search。

PS. We shall maintain the monotonicity in each round of Seach, otherwise, we shall have specail check to filter those case.

For example :