- 能使用二分搜索的前提是數(shù)組已排序密浑。
- 二分查找的使用場(chǎng)景：（1）可轉(zhuǎn)換為find the first/last position of...（2）時(shí)間復(fù)雜度至少為O(lgn)戴陡。
- 遞歸和迭代的使用場(chǎng)景：能用迭代就用迭代仆嗦，特別復(fù)雜時(shí)采用遞歸弃锐。
Ref:https://algorithm.yuanbin.me/zh-hans/binary_search/binary_search.md
leetcode 374
We are playing the Guess Game. The game is as follows:
I pick a number from 1 to n. You have to guess which number I picked.
Every time you guess wrong, I'll tell you whether the number is higher or lower.
You call a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0):
-1 : My number is lower
1 : My number is higher
0 : Congrats! You got it!
Example:
n = 10, I pick 6.
Return 6.
public int guessNumber(int n) {
int start = 1;
int end = n;
int mid;
int tmp;
while(start < end){
mid = start/2 + end/2;
tmp = guess(mid);
if ( tmp == 0) return mid;
else if ( tmp == 1){
start = mid + 1;
} else{
end = mid - 1;
}
}
return start;
}
在上述程序中
mid = start/2 + end/2;
這里之所以這樣寫是防止兩數(shù)相加后溢出遏佣。
while(start < end)
循環(huán)判斷不取等號(hào)可以防止死循環(huán)白粉。
當(dāng)涉及數(shù)組時(shí)掩缓，我們經(jīng)常會(huì)發(fā)生數(shù)組越界的情況雪情，這種時(shí)候我們可以采取補(bǔ)項(xiàng)的思路。
定義 lower bound 為在給定升序數(shù)組中大于等于目標(biāo)值的最小索引你辣，upper bound 則為小于等于目標(biāo)值的最大索引.以lower bound為例：
public static int lowerBound(int[] nums, int target) {
if (nums == null || nums.length == 0) return -1;
int lb = -1, ub = nums.length;
while (lb + 1 < ub) {
int mid = lb + (ub - lb) / 2;
if (nums[mid] < target) {
lb = mid;
} else {
ub = mid;
}
}
return lb + 1;
}
這里我們采取巡通，使lb尘执，ub在數(shù)組邊界的兩端+1，而不是剛好等于數(shù)組邊界宴凉。
int lb = -1, ub = nums.length;
如果遇到有問插入索引的位置時(shí)誊锭，可以分三種典型情況：
1.目標(biāo)值在數(shù)組范圍之內(nèi)，最后返回值一定是 lb + 1
2.目標(biāo)值比數(shù)組最小值還小弥锄，此時(shí) lb 一直為 -1 , 故最后返回 lb + 1 也沒錯(cuò)丧靡，也可以將 -1 理解為數(shù)組前一個(gè)更小的值
3.目標(biāo)值大于等于數(shù)組最后一個(gè)值，由于循環(huán)退出條件為 lb + 1 == ub , 那么循環(huán)退出時(shí)一定有 lb = A.length - 1 , 應(yīng)該返回 lb + 1
