1.簡介
二分查找即搜索一個數(shù)，如果存在元媚，返回其索引配乓，否則返回 -1』莼伲基本框架：
int binarySearch(int[] nums, int target) {
int left = 0, right = ...;
while(...) {
int mid = (left + right) / 2;//小細(xì)節(jié)
if (nums[mid] == target) {
...
} else if (nums[mid] < target) {
left = ...
} else if (nums[mid] > target) {
right = ...
}
}
return ...;
}
分析二分查找的一個技巧是：不要出現(xiàn) else，而是把所有情況用 else if 寫清楚崎页，這樣可以清楚地展現(xiàn)所有細(xì)節(jié)鞠绰。本文都會使用 else if，目的就是講清楚飒焦，大家理解后可自行簡化蜈膨。
2.常見問題
- while里到底是 <= 還是 <
- mid是+1還是不變？
- target有多個的時候怎么辦牺荠？
3.沒有重復(fù)值
int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1; // 注意
while(left <= right) {
int mid = left + (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)的條件中是 <=，而不是 <休雌？
答：因為初始化 right 的賦值是 nums.length - 1灶壶，即最后一個元素的索引，而不是 nums.length杈曲。
這二者可能出現(xiàn)在不同功能的二分查找中驰凛，區(qū)別是：前者相當(dāng)于兩端都閉區(qū)間 [left, right]胸懈，后者相當(dāng)于左閉右開區(qū)間 [left, right)，因為索引大小為 nums.length 是越界的恰响。
我們這個算法中使用的是前者 [left, right] 兩端都閉的區(qū)間趣钱。這個區(qū)間其實(shí)就是每次進(jìn)行搜索的區(qū)間。
什么時候應(yīng)該停止搜索呢胚宦？當(dāng)然首有，找到了目標(biāo)值的時候可以終止：
if(nums[mid] == target)
return mid;
但如果沒找到，就需要 while 循環(huán)終止枢劝，然后返回 -1井联。那 while 循環(huán)什么時候應(yīng)該終止？搜索區(qū)間為空的時候應(yīng)該終止呈野，意味著你沒得找了低矮，就等于沒找到嘛。
while(left <= right) 的終止條件是 left == right + 1被冒，寫成區(qū)間的形式就是 [right + 1, right]军掂，或者帶個具體的數(shù)字進(jìn)去 [3, 2]，可見這時候區(qū)間為空昨悼，因為沒有數(shù)字既大于等于 3 又小于等于 2 的吧蝗锥。所以這時候 while 循環(huán)終止是正確的，直接返回 -1 即可率触。
while(left < right) 的終止條件是 left == right终议，寫成區(qū)間的形式就是 [left, right]，或者帶個具體的數(shù)字進(jìn)去 [2, 2]葱蝗，這時候區(qū)間非空穴张，還有一個數(shù) 2，但此時 while 循環(huán)終止了两曼。也就是說這區(qū)間 [2, 2] 被漏掉了皂甘，索引 2 沒有被搜索，如果這時候直接返回 -1 就是錯誤的悼凑。
當(dāng)然偿枕，如果你非要用 while(left < right) 也可以，我們已經(jīng)知道了出錯的原因户辫，就打個補(bǔ)丁好了：
//...
while(left < right) {
// ...
}
return nums[left] == target ? left : -1;
2渐夸、為什么 left = mid + 1，right = mid - 1渔欢？我看有的代碼是 right = mid 或者 left = mid墓塌，沒有這些加加減減，到底怎么回事，怎么判斷桃纯？
答：這也是二分查找的一個難點(diǎn)酷誓，不過只要你能理解前面的內(nèi)容，就能夠很容易判斷态坦。
剛才明確了「搜索區(qū)間」這個概念盐数，而且本算法的搜索區(qū)間是兩端都閉的，即 [left, right]伞梯。那么當(dāng)我們發(fā)現(xiàn)索引 mid 不是要找的 target 時玫氢，下一步應(yīng)該去搜索哪里呢？
當(dāng)然是去搜索 [left, mid-1] 或者 [mid+1, right] 對不對谜诫？因為 mid 已經(jīng)搜索過漾峡，應(yīng)該從搜索區(qū)間中去除。
3喻旷、此算法有什么缺陷生逸？
答：至此，你應(yīng)該已經(jīng)掌握了該算法的所有細(xì)節(jié)且预，以及這樣處理的原因槽袄。但是，這個算法存在局限性锋谐。
比如說給你有序數(shù)組 nums = [1,2,2,2,3]遍尺，target 為 2，此算法返回的索引是 2涮拗，沒錯乾戏。但是如果我想得到 target 的左側(cè)邊界，即索引 1三热，或者我想得到 target 的右側(cè)邊界鼓择，即索引 3，這樣的話此算法是無法處理的就漾。
這樣的需求很常見惯退，你也許會說，找到一個 target从藤，然后向左或向右線性搜索不行嗎？可以锁蠕，但是不好夷野，因為這樣難以保證二分查找對數(shù)級的復(fù)雜度了。
我們后續(xù)的算法就來討論這兩種二分查找的算法荣倾。
4.尋找左側(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; // 注意
}
}
// target 比所有數(shù)都大
if (left == nums.length) return -1;
// 類似之前算法的處理方式
return nums[left] == target ? left : -1;
}
1、為什么 while 中是 < 而不是 <=?
答：用相同的方法分析舌仍，因為 right = nums.length 而不是 nums.length - 1妒貌。因此每次循環(huán)的「搜索區(qū)間」是 [left, right) 左閉右開通危。
while(left < right) 終止的條件是 left == right，此時搜索區(qū)間 [left, left) 為空灌曙，所以可以正確終止菊碟。
PS：這里先要說一個搜索左右邊界和上面這個算法的一個區(qū)別，也是很多讀者問的：剛才的 right 不是 nums.length - 1 嗎在刺，為啥這里非要寫成 nums.length 使得「搜索區(qū)間」變成左閉右開呢逆害？
因為對于搜索左右側(cè)邊界的二分查找，這種寫法比較普遍蚣驼，我就拿這種寫法舉例了魄幕，保證你以后遇到這類代碼可以理解。你非要用兩端都閉的寫法反而更簡單颖杏，我會在后面寫相關(guān)的代碼纯陨，把三種二分搜索都用一種兩端都閉的寫法統(tǒng)一起來，你耐心往后看就行了留储。
2翼抠、為什么沒有返回 -1 的操作？如果 nums 中不存在 target 這個值欲鹏，怎么辦机久？
答：因為要一步一步來，先理解一下這個「左側(cè)邊界」有什么特殊含義：
對于這個數(shù)組赔嚎，算法會返回 1膘盖。這個 1 的含義可以這樣解讀：nums 中小于 2 的元素有 1 個。
比如對于有序數(shù)組 nums = [2,3,5,7], target = 1尤误，算法會返回 0侠畔，含義是：nums 中小于 1 的元素有 0 個。
再比如說 nums = [2,3,5,7], target = 8损晤，算法會返回 4软棺，含義是：nums 中小于 8 的元素有 4 個。
綜上可以看出尤勋，函數(shù)的返回值（即 left 變量的值）取值區(qū)間是閉區(qū)間 [0, nums.length]喘落，所以我們簡單添加兩行代碼就能在正確的時候 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 瘦棋？和之前的算法不一樣？
答：這個很好解釋暖哨，因為我們的「搜索區(qū)間」是 [left, right) 左閉右開赌朋，所以當(dāng) nums[mid] 被檢測之后，下一步的搜索區(qū)間應(yīng)該去掉 mid 分割成兩個區(qū)間，即 [left, mid) 或 [mid + 1, right)沛慢。
4赡若、為什么該算法能夠搜索左側(cè)邊界？
答：關(guān)鍵在于對于 nums[mid] == target 這種情況的處理：
if (nums[mid] == target)
right = mid;
可見团甲，找到 target 時不要立即返回逾冬，而是縮小「搜索區(qū)間」的上界 right，在區(qū)間 [left, mid) 中繼續(xù)搜索伐庭，即不斷向左收縮粉渠，達(dá)到鎖定左側(cè)邊界的目的。
5圾另、為什么返回 left 而不是 right霸株？
答：都是一樣的，因為 while 終止的條件是 left == right集乔。
6去件、能不能想辦法把 right 變成 nums.length - 1，也就是繼續(xù)使用兩邊都閉的「搜索區(qū)間」扰路？這樣就可以和第一種二分搜索在某種程度上統(tǒng)一起來了尤溜。
答：當(dāng)然可以，只要你明白了「搜索區(qū)間」這個概念汗唱，就能有效避免漏掉元素宫莱，隨便你怎么改都行。下面我們嚴(yán)格根據(jù)邏輯來修改：
因為你非要讓搜索區(qū)間兩端都閉哩罪，所以 right 應(yīng)該初始化為 nums.length - 1授霸，while 的終止條件應(yīng)該是 left == right + 1，也就是其中應(yīng)該用 <=：
int left_bound(int[] nums, int target) {
// 搜索區(qū)間為 [left, right]
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
// if else ...
}
因為搜索區(qū)間是兩端都閉的际插，且現(xiàn)在是搜索左側(cè)邊界碘耳，所以 left 和 right 的更新邏輯如下：
if (nums[mid] < target) {
// 搜索區(qū)間變?yōu)?[mid+1, right]
left = mid + 1;
} else if (nums[mid] > target) {
// 搜索區(qū)間變?yōu)?[left, mid-1]
right = mid - 1;
} else if (nums[mid] == target) {
// 收縮右側(cè)邊界
right = mid - 1;
}
由于 while 的退出條件是 left == right + 1，所以當(dāng) target 比 nums 中所有元素都大時框弛，會存在以下情況使得索引越界：
因此辛辨，最后返回結(jié)果的代碼應(yīng)該檢查越界情況：
if (left >= nums.length || nums[left] != target)
return -1;
return left;
至此，整個算法就寫完了瑟枫，完整代碼如下：
int left_bound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
// 搜索區(qū)間為 [left, right]
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
// 搜索區(qū)間變?yōu)?[mid+1, right]
left = mid + 1;
} else if (nums[mid] > target) {
// 搜索區(qū)間變?yōu)?[left, mid-1]
right = mid - 1;
} else if (nums[mid] == target) {
// 收縮右側(cè)邊界
right = mid - 1;
}
}
// 檢查出界情況
if (left >= nums.length || nums[left] != target)
return -1;
return left;
}
這樣就和第一種二分搜索算法統(tǒng)一了斗搞，都是兩端都閉的「搜索區(qū)間」，而且最后返回的也是 left 變量的值慷妙。只要把住二分搜索的邏輯榜旦，兩種形式大家看自己喜歡哪種記哪種吧。
4景殷、尋找右側(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、為什么這個算法能夠找到右側(cè)邊界绩蜻？
答：類似地铣墨，關(guān)鍵點(diǎn)還是這里：
if (nums[mid] == target) {
left = mid + 1;
當(dāng) nums[mid] == target 時，不要立即返回办绝，而是增大「搜索區(qū)間」的下界 left伊约，使得區(qū)間不斷向右收縮，達(dá)到鎖定右側(cè)邊界的目的孕蝉。
2屡律、為什么最后返回 left - 1 而不像左側(cè)邊界的函數(shù)，返回 left****降淮？而且我覺得這里既然是搜索右側(cè)邊界超埋，應(yīng)該返回 right 才對。
答：首先佳鳖，while 循環(huán)的終止條件是 left == right霍殴，所以 left 和 right 是一樣的，你非要體現(xiàn)右側(cè)的特點(diǎn)系吩，返回 right - 1 好了来庭。
至于為什么要減一，這是搜索右側(cè)邊界的一個特殊點(diǎn)穿挨，關(guān)鍵在這個條件判斷：
if (nums[mid] == target) {
left = mid + 1;
// 這樣想: mid = left - 1
因為我們對 left 的更新必須是 left = mid + 1月弛，就是說 while 循環(huán)結(jié)束時，nums[left] 一定不等于 target 了絮蒿，而 nums[left-1] 可能是 target尊搬。
至于為什么 left 的更新必須是 left = mid + 1，同左側(cè)邊界搜索土涝，就不再贅述佛寿。
3、為什么沒有返回 -1 的操作但壮？如果 nums 中不存在 target 這個值冀泻，怎么辦？
答：類似之前的左側(cè)邊界搜索蜡饵，因為 while 的終止條件是 left == right弹渔，就是說 left 的取值范圍是 [0, nums.length]，所以可以添加兩行代碼溯祸，正確地返回 -1：
while (left < right) {
// ...
}
if (left == 0) return -1;
return nums[left-1] == target ? (left-1) : -1;
4肢专、是否也可以把這個算法的「搜索區(qū)間」也統(tǒng)一成兩端都閉的形式呢舞肆？這樣這三個寫法就完全統(tǒng)一了，以后就可以閉著眼睛寫出來了博杖。
答：當(dāng)然可以椿胯，類似搜索左側(cè)邊界的統(tǒng)一寫法，其實(shí)只要改兩個地方就行了：
int right_bound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) {
// 這里改成收縮左側(cè)邊界即可
left = mid + 1;
}
}
// 這里改為檢查 right 越界的情況剃根，見下圖
if (right < 0 || nums[right] != target)
return -1;
return right;
}
當(dāng) target 比所有元素都小時哩盲，right 會被減到 -1，所以需要在最后防止越界：
至此狈醉，搜索右側(cè)邊界的二分查找的兩種寫法也完成了廉油，其實(shí)將「搜索區(qū)間」統(tǒng)一成兩端都閉反而更容易記憶，你說是吧苗傅？
5抒线、邏輯統(tǒng)一
來梳理一下這些細(xì)節(jié)差異的因果邏輯：
第一個，最基本的二分查找算法：
因為我們初始化 right = nums.length - 1
所以決定了我們的「搜索區(qū)間」是 [left, right]
所以決定了 while (left <= right)
同時也決定了 left = mid+1 和 right = mid-1
因為我們只需找到一個 target 的索引即可
所以當(dāng) nums[mid] == target 時可以立即返回
第二個金吗，尋找左側(cè)邊界的二分查找：
因為我們初始化 right = nums.length
所以決定了我們的「搜索區(qū)間」是 [left, right)
所以決定了 while (left < right)
同時也決定了 left = mid + 1 和 right = mid
因為我們需找到 target 的最左側(cè)索引
所以當(dāng) nums[mid] == target 時不要立即返回
而要收緊右側(cè)邊界以鎖定左側(cè)邊界
第三個十兢，尋找右側(cè)邊界的二分查找：
因為我們初始化 right = nums.length
所以決定了我們的「搜索區(qū)間」是 [left, right)
所以決定了 while (left < right)
同時也決定了 left = mid + 1 和 right = mid
因為我們需找到 target 的最右側(cè)索引
所以當(dāng) nums[mid] == target 時不要立即返回
而要收緊左側(cè)邊界以鎖定右側(cè)邊界
又因為收緊左側(cè)邊界時必須 left = mid + 1
所以最后無論返回 left 還是 right，必須減一
對于尋找左右邊界的二分搜索摇庙，常見的手法是使用左閉右開的「搜索區(qū)間」旱物，我們還根據(jù)邏輯將「搜索區(qū)間」全都統(tǒng)一成了兩端都閉，便于記憶卫袒，只要修改兩處即可變化出三種寫法：
int binary_search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while(left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if(nums[mid] == target) {
// 直接返回
return mid;
}
}
// 直接返回
return -1;
}
int left_bound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) {
// 別返回宵呛，鎖定左側(cè)邊界
right = mid - 1;
}
}
// 最后要檢查 left 越界的情況
if (left >= nums.length || nums[left] != target)
return -1;
return left;
}
int right_bound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) {
// 別返回，鎖定右側(cè)邊界
left = mid + 1;
}
}
// 最后要檢查 right 越界的情況
if (right < 0 || nums[right] != target)
return -1;
return right;
}
六夕凝、參考
1.labuladong的算法精講
