目錄
??前言??
?? 樸素二分查找
??? 樸素二分模板
?? 查找區(qū)間端點處
細節(jié)（重要）
??? 區(qū)間左端點處模板
??? 區(qū)間右端點處模板
?? 習(xí)題
1.?35. 搜索插入位置 - 力扣（LeetCode）
2.?69. x 的平方根 - 力扣（LeetCode）
3.153. 尋找旋轉(zhuǎn)排序數(shù)組中的最小值 - 力扣（LeetCode）
4.?LCR 173. 點名 - 力扣（LeetCode） ? ? ? ?
5.?852. 山脈數(shù)組的峰頂索引 - 力扣（LeetCode）
6.162. 尋找峰值 - 力扣（LeetCode）
?? 總結(jié)
??前言??
? ? ? ? 歡迎觀看本期【算法雜貨鋪】，本期內(nèi)容將講解基礎(chǔ)算法中的——二分算法。二分查找算法，就是利用二段性，將問題劃分成兩個區(qū)間，去掉一個區(qū)間，在另一個區(qū)間查找答案。
? ? ? ? 二分查找是有模板供大家使用的，即背下模板，只需要略微修改即可，但本文旨在理解這些模板。
? ? ? ? 本篇文章通過講解例題，帶大家快速了解二分算法，分為3步，講解各個二分算法。1. 題目解析；2. 算法思路；3. 代碼展示。
?? 樸素二分查找
704. 二分查找 - 力扣（LeetCode）
1. 題目解析
? ? ? ? 相信有一點語言基礎(chǔ)的人都會這道題目，我們只需要遍歷一遍這個數(shù)組即可，如果找到范圍下標(biāo)，沒有找到返回-1，但是這種暴力解法，時間復(fù)雜度是O(N)。
? ? ? ? 這里我們還有一個初始條件沒有用到，即n個元素使有序的（升序）。
2. 算法原理
? ? ? ? 上圖中，我們通過在一個數(shù)組中查找7，給大家展示了二分算法的基本思路。即根據(jù)某種規(guī)則，將區(qū)間劃分成兩端，再根據(jù)規(guī)則，舍去一端區(qū)間，在另一端區(qū)間內(nèi)查找。
結(jié)束條件：
? ? ? ? 當(dāng) left >?right 的時候，不存在區(qū)間，循環(huán)結(jié)束。為什么left可以等于right呢，當(dāng)只有1個元素的時候，也是要查找的 , 即 (left + right )/2 = right = left 的。
????????
為什么是正確的：
? ? ? ? 二分算法是利用二段行進行查找的，這道題的二段性體現(xiàn)在數(shù)組是有序的。在暴力算法中，我們是一個個比較的，在二分算法中，我們是按區(qū)間比較的，即[ left , mid-1 ] 和 [ mid+1 , right]。
時間復(fù)雜度：
????????我們只需要看循環(huán)了多少次即可，只要left <= right的時候，就進循環(huán)，當(dāng)問題規(guī)模n就除2。
? ? ? ? ? 當(dāng)left == right的時候，數(shù)組中只剩下一個元素，所以執(zhí)行x次后，問題規(guī)模就為1。
3. 代碼展示
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while(left <= right)
{
//優(yōu)化：防止溢出
int mid = left + (right - left)/2;
if(nums[mid] == target)
{
return mid;
}
else if(nums[mid] > target)
{
right = mid - 1;
}
else{
left = mid + 1;
}
}
return -1;
}
};??? 樸素二分模板
while(left <= right)
{
//優(yōu)化：防止溢出
int mid = left + (right - left)/2
if(...)
left = mid + 1;
else if(...)
right = mid - 1;
else
return mid;
}? ? ? ? mid = left + (right - left) /2 是進行了優(yōu)化的，因為當(dāng)left 和 right都很大時，很容易超出int類型的范圍。mid = left + (right - left + 1) / 2在樸素二分模板中也是可以的。
? ? ? ? +1的區(qū)別在于，偶數(shù)個數(shù)時，是向上取整，還是向下取整。
向下取整：left + ( right - left ) / 2
向下取整：left + (right - left + 1) / 2
?? 查找區(qū)間端點處
34. 在排序數(shù)組中查找元素的第一個和最后一個位置 - 力扣（LeetCode）
1. 題目解析
? ? ? ? 依舊先從簡單看起，暴力解法就是先從前往后遍歷，找到第一個位置，如果找到，接著從后往前遍歷，查找最后一個位置，范圍begin和end。否則返回-1，-1。
? ? ? ? 暴力解法的時間復(fù)雜度是O(N)的，但題目要求我們在O(logN)的時間復(fù)雜度。在基礎(chǔ)算法中，很少有算法能優(yōu)化的logN，二分算法就是其中之一。
? ? ? ? 這道題目也是一道非常經(jīng)典的二分查找算法，即查找區(qū)間的左端點，和區(qū)間的右端點。
2. 算法原理
? ? ? ? 用的還是二分算法，即二段行，根據(jù)數(shù)據(jù)的性質(zhì)，在某種判斷條件下將區(qū)間一分為二（不一定是有序，有二段性即可。）舍去一個區(qū)間，在另一個區(qū)間內(nèi)查找。
尋找左端點思路：
? ? ? ? 左區(qū)間：[ left , result - 1 ] 都是嚴格小于 t 的。
? ? ? ? 右區(qū)間: [ result , right?] 都是嚴格大于等于 t 的。
???????
? ? ? ? 因此，關(guān)于mid的落點，我們可以分為下面這兩種情況：
? ? ? ? 1. 當(dāng) mid 落在[ left , result - 1 ] 區(qū)間的時候，即 nums[mid] < t 。說明 [left , mid ]都是可以舍去的，此時更新left到mid+1的位置，繼續(xù)在 [ mid +1 , right] 上尋找左邊界。
? ? ? ? 2. 當(dāng)mid 落在[result , right]區(qū)間的時候，即 nums[mid] >= t。說明[mid +1 ,right]的區(qū)間可以社區(qū)（mid可能是最終結(jié)果，也可能不是），繼續(xù)在[left,mid]上查找左端點。
注意的是，尋找左端點時，采用向下取整。
? ? ? ? 左指針的變化：left = mid + 1,區(qū)間逐漸減少。
? ? ? ? 右指針的變化：right = mid ，可能會原地踏步。如果采用向上取整，可能會死循環(huán)，例如：t = 2 , mid = left + (right - left + 1)/2的話，right = mid，mid = right陷入死循環(huán)。
//查找區(qū)間左端點
int left =0;
int right = nums.size()-1;
while(left < right)
{
int mid = left + (right - left)/2;
if(nums[mid] >= target)
{
right = mid;
}
else
{
left = mid + 1;
}
}?尋找右端點思路：
? ? ? ?左區(qū)間：[ left , result ] 都是嚴格小于等與t的。
? ? ? ?右區(qū)間：[ result+1 ， right ]?都是嚴格大于t的。
? ? ? ? 1. 當(dāng)mid落在左區(qū)間時，mid可能是最終結(jié)果，也可能不是，所以 left = mid，舍去區(qū)間[left,mid -1]。繼續(xù)在區(qū)間[ mid , right]區(qū)間內(nèi)查找。
? ? ? ? 2. 當(dāng)mid落在右區(qū)間時，可以舍去[mid , right]的區(qū)間，right = mid - 1。繼續(xù)在區(qū)間[ left , mid -1 ]內(nèi)查找。
注意的是，尋找右端點時，采用向上取整：
? ? ? ? 右指針的變化：right = mid - 1，區(qū)間逐漸減少。
? ? ? ? 左指針的變化：left = mid，可能會原地踏步，采用向下取整，可能會陷入死循環(huán)。例如：t =1 ,mid = left + (right - left) / 2
//查找區(qū)間右端點
left = 0;
right = nums.size()-1;
while(left < right)
{
int mid = left +(right-left+1)/2;
if(nums[mid] <= target)
{
left = mid;
}
else
{
right = mid -1;
}
}細節(jié)（重要）
?（1） 循環(huán)條件?
? ? ? ? ? ? ? ? left < right。我們以尋找右端點為例：
? ? ? ? left的工作區(qū)間就是在小于等于t這個區(qū)間；right的工作區(qū)間就是在大于t這個區(qū)間。因為right = mid - 1,所以right跳出工作區(qū)間時，一定是在right == left的位置。
? ? ? ? 所以不需要判斷right是否等于left，是一定等于的。
???????
（2） 求中點操作??
? ? ? ? 其實，我們只需要記住，下面有-1的時候，上面就有+1,。其他的結(jié)合題意給出二段行的判斷條件。
3. 代碼展示
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if(nums.size() == 0)
{
return {-1,-1};
}
//查找區(qū)間左端點
int left =0;
int right = nums.size()-1;
while(left < right)
{
int mid = left + (right - left)/2;
if(nums[mid] >= target)
{
right = mid;
}
else
{
left = mid + 1;
}
}
if(nums[left] != target)
{
return {-1,-1};
}
int begin = left;
//查找區(qū)間右端點
left = 0;
right = nums.size()-1;
while(left < right)
{
int mid = left +(right-left+1)/2;
if(nums[mid] <= target)
{
left = mid;
}
else
{
right = mid -1;
}
}
int end = right;
return {begin,end};
}
};??? 區(qū)間左端點處模板
while(left < right)
{
int mid = left + (right - left)/2;
if(...)
left = mid + 1;
else
right = mid;
}??? 區(qū)間右端點處模板
while(left < right)
{
int mid = left + (right - left)/2;
if(...)
left = mid;
else
right = mid - 1;
}? ? ? ? 以上，就將二分算法的所有知識點講解完畢，其中樸素二分模板是容易理解的，后面兩個二分模板還是需要大家自己畫圖不斷加強理解的。
? ? ? ? 下面，我們通過幾道習(xí)題加強理解。對于習(xí)題，不會再過多講解知識點內(nèi)容，而是直接給出題解思路，并配圖加強理解和做題能力。
?? 習(xí)題
1.?35. 搜索插入位置 - 力扣（LeetCode）
? ? ? ? 我們通過畫圖，可以看出來，這是一道非常經(jīng)典的查找區(qū)間左端點的題，找到大于等于t的第一個點即可。????????
????????如果t不存在在數(shù)組中，則返回left+1（left 經(jīng)過循環(huán)來到right這個位置，即最后一個位置）
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left = 0;
int right = nums.size()-1;
while(left < right)
{
int mid = left + (right - left) / 2;
if(nums[mid] >= target)
right = mid;
else
left = mid + 1;
}
return nums[left] < target ? left + 1:left;
}
};2.?69. x 的平方根 - 力扣（LeetCode）
? ? ? ? 其實這道題，你用二分查找左端點，或者查找右端點都可以做出來。這里我們就以查找右端點為例，當(dāng)然，也會展示左端點的解法。
? ? ? ? 前面需要特殊判斷x是否小于1，如果小于1，則返回0。
class Solution {
public:
int mySqrt(int x) {
if(x < 1)
{
return 0;
}
int left = 1;
int right = x;
while(left < right)
{
long long mid = left + (right - left + 1)/2;
if(mid * mid <= x)
left = mid;
else
right = mid - 1;
}
return right;
}
};? ? ? ? 以上是查找右端點的寫法，當(dāng)然也可以寫成查找左端點。
? ? ? ? 不過因為，查找左端點，數(shù)值是會比查找右端點大的多，所以，left 和 right都采用 long long類型。最后判斷一下，right的平方是否等于x，如果不等于返回right-1。
class Solution {
public:
int mySqrt(int x) {
long long left = 0;
long long right = x;
while(left < right)
{
long long mid = left + (right - left) / 2;
if(mid * mid < x)
{
left = mid + 1;
}
else
{
right = mid;
}
}
return right*right == x?right:right-1;
}
};? ? ? ? 這道題，可以很好的理解二分法，即一道題往往不止一種解決方法。
3.153. 尋找旋轉(zhuǎn)排序數(shù)組中的最小值 - 力扣（LeetCode）
? ? ? ? 通過題意，可以了解的是，旋轉(zhuǎn)就是將最后一個元素移動到最開始的位置。此外，還有一個重要條件就是 互不相同。
? ? ? ? 那我們就可以利用互不相同，得出二段行，如下圖所示。
? ? ?????因此，我么以D點的值為索引，
? ? ? ? 當(dāng)mid落在區(qū)間[A,B]時，left = mid + 1。[A,B]區(qū)間內(nèi)的點是嚴格大于D點的值。
? ? ? ? 當(dāng)mid落在區(qū)間[C,D]時，right = mid。其中C點就是我們要求的點。C點的值是要個小于D點的值。當(dāng)[C,D]區(qū)間內(nèi)只有一個元素時，C點的值可能等于D點的值。
class Solution {
public:
int findMin(vector<int>& nums) {
int x = nums[nums.size()-1];
int left = 0;
int right = nums.size()-1;
while(left < right)
{
int mid = left + (right - left ) / 2;
if(nums[mid] > x)
{
left = mid + 1;
}
else
{
right = mid;
}
}
return nums[right];
}
};4.?LCR 173. 點名 - 力扣（LeetCode） ? ? ? ?
???????????????數(shù)組中，下標(biāo)等于元素值，如果有一位同學(xué)缺席，那么它之后所有元素的下標(biāo)就不等于元素的值。
? ? ? ? 因此，我們只需要查找左端點即可。
????????此外，這道題還需要注意的是，最后需要處理一下邊界情況，如數(shù)組中僅有一個元素1，那么缺席的同學(xué)編號就是0；如果僅有一個元素0，那么缺席的同學(xué)編號為1。
class Solution {
public:
int takeAttendance(vector<int>& records) {
int left = 0;
int right = records.size()-1;
while(left < right)
{
int mid = left + (right - left) / 2;
if(records[mid] == mid)
{
left = mid + 1;
}
else
{
right = mid;
}
}
return records[right] == right?right+1:right;
}
};5.?852. 山脈數(shù)組的峰頂索引 - 力扣（LeetCode）
? ? ? ? 這道題目，查找左端點或查找右端點都可以，這里我們就以查找右端點為例，不在講解如何查找左端點，感興趣可以自己實踐一下。
???????
? ? ? ? 當(dāng)mid處于上升區(qū)間時，在[mid + 1， right]區(qū)間查找。
? ? ? ? 當(dāng)mid處于下降區(qū)間時，在[left , mid - 1]區(qū)間查找。
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int left =0;
int right = arr.size() -1;
while(left < right)
{
int mid = left + (right - left)/2;
if(arr[mid] < arr[mid+1])
{
left = mid +1;
}
else
{
right = mid ;
}
}
return right;
}
};6.162. 尋找峰值 - 力扣（LeetCode）
?尋找?段性：
? ? ? ? 1. 當(dāng)arr[mid] > arr[mid+1],左側(cè)一定存在山峰，到[left,mid]尋找山峰。
? ? ? ? 2. 當(dāng)arr[mid] < arr[mid+1],右側(cè)一定存在山峰，到[mid+1,right]尋找。
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int left =0;
int right = nums.size()-1;
while(left < right)
{
int mid = left + (right - left) / 2;
if(nums[mid] < nums[mid+1])
{
left = mid + 1;
}
else
{
right = mid;
}
}
return left;
}
};?? 總結(jié)
? ? ? ? 以上，我們就將二分算法帶大家做了全面了解。二分算法的核心就是尋找二段性，有了二段性，直接套模板即可。對于模板，建議是理解著去背誦，效果更好。
? ? ? ? 通過習(xí)題，我們也加強了對二分算法的理解，平時做題中，看到時間復(fù)雜度為logN的，我們應(yīng)該敏銳的想到二分算法。
? ? ? ? 以上就是本期【算法雜貨鋪】的主要內(nèi)容了，如果感覺對你有幫助，歡迎點贊，收藏，關(guān)注。Thanks?(?ω?)?文章來源：http://www.zghlxwxcb.cn/news/detail-849409.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-849409.html
到了這里，關(guān)于【算法雜貨鋪】二分算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
