本文僅為作者自學(xué)之用苇侵，系統(tǒng)為macOS祈争，不保證信息準(zhǔn)確。
用題型來分的話荸恕，二分法可以簡(jiǎn)單分為兩種：
- 對(duì)于一個(gè)沒有重復(fù)的有序數(shù)列咽笼，需要用二分法找到某一個(gè)數(shù)的準(zhǔn)確位置；
int start = 0;
int end = nums.length;
while(start <= end){
mid = start + (end - start)/2;
if(nums[mid]==target){
return mid;
}
if(nums[mid] > target){
end = mid - 1;
}
if(nums[mid] < target){
start = mid + 1;
}
}
return start;
這個(gè)時(shí)候的start的位置滿足以下條件：
- 假如存在target戚炫，那么start就是target的位置
- 假如不存在target剑刑，那么start的位置就是第一個(gè)大于target的數(shù)的位置；
- 假如不存在target双肤，而且數(shù)組末尾數(shù)也比target小施掏，那么start就是數(shù)組的長(zhǎng)度（也就是數(shù)組末尾數(shù)的角標(biāo)數(shù)+1）
為什么start是這個(gè)結(jié)果呢？需要自己窮舉各種不同的輸入來看茅糜，發(fā)現(xiàn)輸出都滿足同一種結(jié)論
2.對(duì)于一個(gè)有重復(fù)的有序數(shù)列七芭，用二分法尋找第一個(gè)大于等于target的數(shù)的位置；
int start = 0;
int end = nums.length;
while(start < end){
mid = start + (end - start)/2;
if(nums[mid] < target){
start = mid + 1;
}
else{
end = mid;
}
}
return start;
這個(gè)程序返回的是第一個(gè)大于等于target的數(shù)的位置蔑赘。
- 如果最小的數(shù)都比target大狸驳，則start為0
- 如果最大的數(shù)都比target小，則start = end = 數(shù)組長(zhǎng)度
- 如果數(shù)組中存在target缩赛，則指向第一個(gè)target（重復(fù)的話）
