二分查找解析 【轉(zhuǎn)】
原文：https://www.cnblogs.com/kyoner/p/11080078.html
推薦大家去閱讀原文签夭，本文摘錄只是為了方便復(fù)習(xí)２场赴穗！
詳細(xì)二分查找算法
本文將詳細(xì)的分析探究最常用的二分查找場(chǎng)景：尋找一個(gè)數(shù)、尋找左側(cè)邊界膀息、尋找右側(cè)邊界般眉。
而且，我們就是要深入細(xì)節(jié)潜支，比如while循環(huán)中的不等號(hào)是否應(yīng)該帶等號(hào)甸赃，mid 是否應(yīng)該加一等等。分析這些細(xì)節(jié)的差異以及出現(xiàn)這些差異的原因冗酿，保證你能靈活準(zhǔn)確地寫出正確的二分查找算法埠对。
二分查找的框架
int binarySearch(int [] nums, int target) {
int left = 0,right =....
while(...) {
int mid = (right + left) / 2;
if( num[mid] == target ) {
...
} else if (nums[mid] < target ) {
left = ....
} else if (nums[mid] > target ) {
right = ...
}
}
return ...
}
分析二分查找的一個(gè)技巧是：不要出現(xiàn) else，而是把所有情況用 else if 寫清楚裁替，這樣可以清楚地展現(xiàn)所有細(xì)節(jié)项玛。本文會(huì)使用 else if，旨在講清楚弱判，讀者理解后可自行簡化襟沮。
其中 ... 標(biāo)記的部分，就是可能出現(xiàn)細(xì)節(jié)問題的地方昌腰，當(dāng)你見到一個(gè)二分查找的代碼時(shí)开伏，首先注意這幾個(gè)地方。后文用實(shí)例分析這些地方能有什么樣的變化剥哑。
另外聲明一下硅则，計(jì)算 mid 時(shí)需要技巧防止溢出，建議寫成：mid = left + (right - left) / 2株婴。本文暫時(shí)忽略這個(gè)問題怎虫。
尋找一個(gè)數(shù)（基本的二分搜索）
這個(gè)場(chǎng)景是最簡單的，可能也是大家最熟悉的困介，即搜索一個(gè)數(shù)大审，如果存在，返回其索引座哩，否則返回 -1
int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1; // 注意
while(left <= right ) { // 注意
int mid = (right + left) / 2;
if(nums[mid] == target)
return mid
else if(nums[mid] < target)
left = mid + 1; // 注意
else if(nums[mid] > target)
right = mid - 1; // 注意
}
return -1;
}
1. 為什么 while 循環(huán)的條件中是 <= , 而不是 < ?
答: 因?yàn)槌跏蓟?right 的賦值時(shí) nums.length - 1, 即最后一個(gè)元素的索引徒扶，而不是 nums.length。
這二者可能出現(xiàn)在不同功能的二分查找中根穷，區(qū)別是：前者相當(dāng)于兩端都閉區(qū)間 [left , right],后者相當(dāng)于左閉右開區(qū)間 [left, right)姜骡，因?yàn)樗饕笮?nums.length 是越界的导坟。
我們這個(gè)算法中使用的是 [left, right] 兩端都閉的區(qū)間，這個(gè)區(qū)間就是每次進(jìn)行搜索的區(qū)間圈澈，我們不妨成為[搜索區(qū)間](search space)
什么時(shí)候應(yīng)該停止搜索呢? 當(dāng)然找到了目標(biāo)值的時(shí)候可以終止：
if(nums[mid] == target)
return mid;
但是如果沒找到惫周，就需要 while 循環(huán)終止，然后返回 -1康栈。那 while 循環(huán)什么時(shí)候應(yīng)該終止?搜索區(qū)間為空的時(shí)候應(yīng)該終止递递，意味著你沒得找了，就等于沒找到嘛啥么。
while(left <= right) 的終止條件是 left == right + 1登舞，寫成區(qū)間的形式就是 [right + 1, right]，或者帶個(gè)具體的數(shù)字進(jìn)去 [3,2]悬荣，可見這個(gè)時(shí)候搜索區(qū)間為空菠秒，因?yàn)闆]有數(shù)字既大于3又小于等于2的吧？
所以這個(gè)時(shí)候 while 循環(huán)終止是正確的隅熙，直接返回 -1 即可
while(left < right) 的終止條件是 left == right稽煤，寫成區(qū)間的形式就是[right,right]，或者帶個(gè)具體數(shù)字進(jìn)去[2,2]囚戚，這個(gè)時(shí)候收縮區(qū)間非空酵熙，還有一個(gè)數(shù)2，但此時(shí) while 循環(huán)終止了驰坊。也就是說這個(gè)區(qū)間 [2,2] 被漏掉了匾二，索引 2 沒有被搜索，如果這時(shí)候直接返回 -1 就可能出現(xiàn)錯(cuò)誤拳芙。
當(dāng)然如果你非要用 while(left < right) 也可以察藐，我們已經(jīng)知道了出錯(cuò)的原因，就打個(gè)補(bǔ)丁好了：
while(left < right){
// ...
}
return nums[left] == target ? left : -1;
2. 為什么 left = mid + 1, right = mid - 1? 我看有的代碼是 right = mid 或者 left = mid,沒有這些加加減減舟扎，到底怎么回事分飞，要怎么判斷?
答:這也是二分查找的一個(gè)難點(diǎn)，不過只要你能理解前面的內(nèi)容睹限，就很容易判斷了譬猫。
剛才明確了 [搜索空間] 這個(gè)概念，而且本算法的搜索區(qū)間是兩端都閉的羡疗，即[left,right]染服。那么當(dāng)我們發(fā)現(xiàn)索引 mid 不是要找的 target 時(shí)，如何確定下一步的搜索空間呢?
當(dāng)然是去搜索 [left, mid - 1] 或者 [left + 1,right] 對(duì)不對(duì)叨恨？因?yàn)?mid 已經(jīng)搜索過柳刮，應(yīng)該從搜索區(qū)間中去除。
3. 此算法有什么缺陷?
答:至此，你應(yīng)該已經(jīng)掌握了該算法的所有細(xì)節(jié)秉颗，以及這樣處理痢毒，以及這樣處理的原因。但是站宗，這個(gè)算法存在局限性闸准。
比如說給你有序數(shù)組 nums = [1,2,2,2,3], target = 2, 此算法返回的索引是 2，沒錯(cuò)梢灭。但是如果我想得到 target 的左側(cè)邊界，即索引 1蒸其，或者我想得到 target 的右側(cè)邊界敏释，即索引 3，這樣的話此算法是無法處理的
這樣的需求很常見摸袁。你也許會(huì)說钥顽，找到一個(gè) target 索引，然后向左或向右線性搜索不行嗎靠汁？可以蜂大，但是不好，因?yàn)檫@樣難以保證二分查找對(duì)數(shù)級(jí)的時(shí)間復(fù)雜度了蝶怔。
我們后續(xù)的算法就是來討論這兩種二分查找的算法奶浦。
尋找左側(cè)邊界的二分搜索
直接看代碼，其中的標(biāo)記是需要注意的細(xì)節(jié)：
int left_bound(int[] nums, int target) {
if(nums.length == 0) return -1;
int left = 0;
int right = nums.length; // 注意
while(left < right) { // 注意
int mid = (left + right) / 2;
if(nums[mid] == target) {
right = mid;
} else if(nums[mid] < target) {
left = mid + 1;
} else if(nums[mid] > target) {
right = mid; // 注意
}
}
return left;
}
1. 為什么 while(left < right) 而不是 <= ?
答:用相同的方法分析踢星，因?yàn)槌跏蓟?right = nums.length 而不是 nums.length - 1澳叉。因此每次循環(huán)的 [搜索區(qū)間] 是 [left,right) 左閉右開的。
while(left < right) 終止的條件是 left == right, 此時(shí)搜索區(qū)間 [left, left) 恰巧為空沐悦，所以可以正確終止成洗。
2. 為什么沒有返回 -1 的操作? 如果 nums 中不存在 target 這個(gè)值，怎么辦?
答:因?yàn)橐徊揭徊絹聿胤瘢壤斫庖幌逻@個(gè) [左側(cè)邊界] 由什么特殊含義:
對(duì)于這個(gè)數(shù)組瓶殃，算法會(huì)返回 1。這個(gè) 1 的含義可以這樣解讀： nums 中小于 2 的元素有 1 個(gè)副签。
比如對(duì)于有序數(shù)組 nums = [2,3,5,7]
target = 1, 算法會(huì)返回 0遥椿，含義是: nums 中小于 1 的元素有 0 個(gè)。
如果 target = 8继薛，算法會(huì)返回 4修壕，含義是：nums 中小于 8 的元素有 4 個(gè)。
綜上可以看出遏考，函數(shù)的返回值（即left變量的值）取值區(qū)間是閉區(qū)間[0, nums.length]慈鸠，所以我們簡單添加兩行代碼就能在正確的時(shí)候 return -1:
while(left < right){
// ...
}
// target 比所有數(shù)都大
if(left == nums.length) return -1;
// 類似之前算法的處理方式
return nums[left] == target ? left : -1
3. 為什么 left = mid + 1， right = mid? 和之前的算法不一樣?
答：這個(gè)很好解釋，因?yàn)槲覀兊?code>[搜索區(qū)間]是[left, right)左閉右開青团，所以當(dāng) nums[mid] 被檢測(cè)之后譬巫，下一步的搜索區(qū)間應(yīng)該去掉 mid 分割成兩個(gè)區(qū)間，即 [left,mid) 或者 [mid + 1, right)
4. 為什么該算法能夠搜索左側(cè)邊界?
答：關(guān)鍵在于對(duì)于 nums[mid] == target 這種情況的處理：
if(nums[mid] == target)
right = mid;
可見督笆，找到 target 時(shí)不要立即返回芦昔，而是縮小[搜索區(qū)間]的上界 right，在區(qū)間[left, mid) 中繼續(xù)搜索娃肿，即不斷向左收縮咕缎，達(dá)到鎖定左側(cè)邊界的目的。
5. 為什么返回 left 而不是 right?
答：返回 left 和 right 都是一樣的料扰，因?yàn)?while 終止的條件是 left == right
尋找右側(cè)邊界的二分查找
尋找右側(cè)邊界和尋找左側(cè)邊界的代碼差不多凭豪，只有兩處不同，已標(biāo)注:
int right_bound(int[] nums, int target) {
if(nums.length == 0) return -1;
int left = 0, right = nums.length;
while(left < right) {
int mid = (left + right) / 2;
if(nums[mid] == target) {
left = mid + 1; // 注意
} else if(nums[mid] < target) {
left = mid + 1
} else if(nums[mid] > target) {
right = mid;
}
}
return left - 1; // 注意
}
1. 為什么這個(gè)算法能夠找到右側(cè)邊界?
答：類似地晒杈，關(guān)鍵點(diǎn)還是這里：
if(nums[mid] == target){
left = mid + 1;
}
當(dāng) nums[mid] == target時(shí)嫂伞，不要立即返回，而是增大[搜索區(qū)間]的下界 left 拯钻，使得區(qū)間不斷向右收縮帖努，達(dá)到鎖定右測(cè)邊界的目的。
2. 為什么最后返回 left - 1 而不像左側(cè)邊界的函數(shù)粪般，返回 left? 而且我覺得這里既然是搜索右側(cè)邊界拼余，應(yīng)該返回right才對(duì)
答：首先，while 循環(huán)的終止條件是 left == right 所以 left 和 right 是一樣的刊驴，你非要體現(xiàn)右側(cè)的特點(diǎn)姿搜，返回 right-1 好了
至于為什么要減一，這是搜索右側(cè)邊界的一個(gè)特殊點(diǎn)捆憎，關(guān)鍵在這個(gè)條件判斷：
if(nums[mid] == target) {
left = mid + 1
// 這樣想：mid = left - 1
}
因?yàn)槲覀儗?duì) left 的更新必須是 left = mid + 1舅柜，就是說 while 循環(huán)結(jié)束時(shí)，nums[left] 一定不等于 target 了躲惰，而 nums[left - 1]可能是target致份。
至于為什么 left 的更新必須是 left = mid + 1，同左側(cè)邊界搜索础拨，就不再贅述氮块。
3.為什么沒有返回 -1 的操作？如果 nums 中不存在 target 這個(gè)值诡宗，怎么辦滔蝉？
答：類似之前的左側(cè)邊界搜索，因?yàn)?while 的終止條件是 left == right塔沃，就是說 left 的取值范圍是 [0, nums.length]蝠引，所以可以添加兩行代碼，正確地返回 -1：
while (left < right) {
// ...
}
if (left == 0) return -1;
return nums[left-1] == target ? (left-1) : -1;
最后總結(jié)
先來梳理一下這些細(xì)節(jié)差異的因果邏輯：
第一個(gè)，最基本的二分查找算法
因?yàn)槲覀兂跏蓟?right = nums.length - 1
所以決定了我們的 搜索區(qū)間 是 [left,right]
所以決定了 while(left <= right)
同時(shí)也決定了 left = mid + 1 和 right = mid -1
因?yàn)槲覀冎恍枰业揭粋€(gè)target 的索引即可
所以當(dāng) nums[mid] == target 的時(shí)候可以立刻返回
第二個(gè)螃概，尋找左側(cè)邊界的二分查找
因?yàn)槲覀兂跏蓟?right = nums.length
所以決定了我們的 收縮區(qū)間 是 [left, right)
所以決定了 while(left < right)
同時(shí)也決定了 left = mid + 1 和 right = mid
因?yàn)槲覀冃枰业絫arget的最左側(cè)索引
所以當(dāng) nums[mid] == target 時(shí)不要立即返回
而要收緊右側(cè)的邊界以鎖定左側(cè)邊界
第三個(gè)矫夯，尋找右邊界的二分查找
因?yàn)槲覀兂跏蓟?right = nums.length
所以決定了我們的 搜索區(qū)間 是 [left,right)
所以決定了 while(left < right)
同時(shí)也決定了 left = mid + 1 和 right = mid
因?yàn)槲覀冃枰业?target 的最右側(cè)索引
所以當(dāng) nums[mid] == target 時(shí)不要立即返回
而要收緊左側(cè)邊界以鎖定右側(cè)邊界
又因?yàn)槭站o左側(cè)邊界時(shí)必須 left = mid + 1
所以最后無論返回 left 還是 right 都必須減一
如果以上內(nèi)容你都能理解，那么你就已經(jīng)明白了二分查找的細(xì)節(jié)了吊洼。
通過上面你學(xué)會(huì)了:
- 分析二分查找代碼時(shí)训貌，不要出現(xiàn)else，全部展開成else if方便理解
- 注意搜索區(qū)間 和 while 的終止條件冒窍，如果存在漏掉的元素递沪，記得最后檢查
- 如果需要搜索左右邊界，只需要 在 nums[mid] == target 時(shí)做出改動(dòng)就好了综液。
以上区拳。
