柚子快報(bào)邀請(qǐng)碼778899分享：算法魅力-二分查找實(shí)戰(zhàn)
柚子快報(bào)邀請(qǐng)碼778899分享：算法魅力-二分查找實(shí)戰(zhàn)
目錄
前言
算法定義
樸素二分模版
二分查找?
?二分的邊界查找
在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置（medium）
?暴力算法
二分查找?
邊界查找分析
?山峰數(shù)組的峰頂
暴力枚舉
二分查找
搜索旋轉(zhuǎn)排序數(shù)組中的最小值（medium）
二分查找
結(jié)束語
前言
在前面我們學(xué)習(xí)了雙指針，以及其中誕生的分支滑動(dòng)窗口，接下來我們將探討其另外一個(gè)“兄弟”-二分查找。本質(zhì)上也是用左右兩個(gè)指針。
這個(gè)算法的前提是我們數(shù)據(jù)是有序排列的，這里的有序并不只是單純的有序，有時(shí)候根據(jù)數(shù)據(jù)的排列我們可以將數(shù)據(jù)劃分為兩個(gè)區(qū)間，可以簡稱為二段性，（兩段區(qū)間是有序的）且根據(jù)問題選擇合適的二分思路，二分算法有基礎(chǔ)的套用也有進(jìn)階的實(shí)現(xiàn)。
算法定義
二分查找算法（Binary Search Algorithm）是一種在有序數(shù)組中查找特定元素的搜索算法。其基本思想是通過不斷將搜索區(qū)間縮小一半來查找目標(biāo)值。以下是二分查找算法的步驟：
首先確定搜索區(qū)間的起始位置（left）和結(jié)束位置（right）。計(jì)算中間位置（mid），通常是(left + right) / 2，為了避免溢出也可以寫成left + (right - left) / 2。有時(shí)候也寫成?left + (right - left+1) / 2，兩者區(qū)別就是在偶數(shù)個(gè)數(shù)據(jù)時(shí)，一個(gè)是取左邊，一個(gè)是取靠中間右邊?？梢岳斫獬上蛳禄蛘呦蛏先≌１容^中間位置的元素與目標(biāo)值：
如果中間位置的元素等于目標(biāo)值，則搜索成功，返回中間位置的索引。如果中間位置的元素小于目標(biāo)值，則將搜索區(qū)間的起始位置設(shè)置為mid + 1，因?yàn)槟繕?biāo)值必定在右側(cè)區(qū)間。如果中間位置的元素大于目標(biāo)值，則將搜索區(qū)間的結(jié)束位置設(shè)置為mid - 1，因?yàn)槟繕?biāo)值必定在左側(cè)區(qū)間。重復(fù)步驟2和3，直到找到目標(biāo)值或者搜索區(qū)間為空（即left > right）。
如果整個(gè)數(shù)組中沒有找到目標(biāo)值，則返回一個(gè)特殊值（如-1）表示未找到。
樸素二分模版
#include
int binarySearch(const std::vector
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid; // 找到目標(biāo)值，返回索引
} else if (nums[mid] < target) {
left = mid + 1; // 在右側(cè)區(qū)間繼續(xù)查找
} else {
right = mid - 1; // 在左側(cè)區(qū)間繼續(xù)查找
}
}
return -1; // 未找到目標(biāo)值
}
二分查找?
704. 二分查找 - 力扣（LeetCode）
本題可以通過暴力枚舉，通過將數(shù)組的數(shù)據(jù)與目標(biāo)值進(jìn)行比較，相等就返回下標(biāo)，不存在就返回-1.
本題也可以直接就二分查找，就像題目標(biāo)題一樣。
class Solution {
public:
int search(vector
int left=0,right=nums.size()-1;
while(left<=right){
int mid=left+(right-left)/2;
if(nums[mid] left=mid+1; else if(nums[mid]>target) right=mid-1; else return mid; } return -1; } }; ?二分的邊界查找 有效利用數(shù)據(jù)的二段性 下面我們將通過一道題來引入進(jìn)階的二分。 在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置（medium） 34. 在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置 - 力扣（LeetCode） ?暴力算法 這道題我們同樣可以通過遍歷數(shù)據(jù)來求得左右位置，一個(gè)從左邊開始查找，一個(gè)從右邊開始查找，相等就保存并返回到數(shù)據(jù)中，代碼實(shí)現(xiàn)也很簡單。 class Solution { public: vector int left=-1,right=-1; int n=nums.size(); for(int i=0;i if(nums[i]==target){ left=i; break; } } for(int j=n-1;j>=0;j--){ if(nums[j]==target){ right=j; break; } } return{left,right}; } }; 但是這道題讓我們?cè)O(shè)置O(logn)的時(shí)間復(fù)雜度，同樣是查找，故我們可以采用二分查找的思路。 只不過這里要左右兩個(gè)值，理所當(dāng)然采用兩次二分查找，本質(zhì)上這道題就是進(jìn)行左右邊界查找。 二分查找? class Solution { public: vector if(nums.size()==0) return{-1,-1}; int left=0,right=nums.size()-1; while(left int mid=left+(right-left)/2; if(nums[mid] left=mid+1; else right=mid; } int begin=left; if(nums[left]!=target) return{-1,-1}; right=nums.size()-1; while(left int mid=left+(right-left+1)/2; if(nums[mid]>target) right=mid-1; else left=mid; } return{begin,right}; } }; 邊界查找分析 方便敘述，用?x 表示該元素， resLeft 表示左邊界， resRight 表示右邊界。 左邊界查找 尋找左邊界思路 左邊區(qū)間 [left, resLeft - 1] 都是小于 x 的； 右邊區(qū)間（包括左邊界） [resLeft, right] 都是大于等于 x 的； 因此，關(guān)于 mid 的落點(diǎn)，我們可以分為下面兩種情況： 當(dāng)mid 落在 [left, resLeft - 1] 區(qū)間的時(shí)候，也就是 arr[mid] < target 。說明 [left, mid] 都是可以舍去的，此時(shí)更新 left 到 mid + 1 的位置， 繼續(xù)在 [mid + 1, right] 上尋找左邊界； 當(dāng) mid 落在 [resLeft， right] 的區(qū)間的時(shí)候，也就是 arr[mid] >= target 。 說明 [mid + 1, right] （因?yàn)?mid 可能是最終結(jié)果，不能舍去）是可以舍去的，此時(shí)更新 right 到 mid 的位置，繼續(xù)在 [left, mid] 上尋找左邊界； 注意：這面找中間元素需要向下取整。 因?yàn)楹罄m(xù)移動(dòng)左右指針的時(shí)候： 左指針： left = mid + 1 ，是會(huì)向后移動(dòng)的，因此區(qū)間是會(huì)縮小的； 右指針： right = mid ，可能會(huì)原地踏步（比如：如果向上取整的話，如果剩下 1,2 兩個(gè)元 素， left == 1 ， right == 2 ， mid == 2 。更新區(qū)間之后， left，right，mid 的 值沒有改變，就會(huì)陷入死循環(huán)）。 因此一定要注意，當(dāng) right = mid 的時(shí)候，要向下取整。 尋找右邊界思路 用 resRight 表示右邊界； 注意到右邊界的特點(diǎn)： 左邊區(qū)間 （包括右邊界） [left, resRight] 都是小于等于 x 的； 右邊區(qū)間 [resRight+ 1, right] 都是大于 x 的； 關(guān)于 mid 的落點(diǎn)，可以分為下面兩種情況： 當(dāng)mid 落在 [left, resRight] 區(qū)間的時(shí)候，說明 [left, mid - 1] （ mid 不可以舍去，因?yàn)橛锌赡苁亲罱K結(jié)果） 都是可以舍去的，此時(shí)更新 left 到 mid 的位置； 當(dāng) mid 落在 [resRight+ 1, right] 的區(qū)間的時(shí)候，說明 [mid, right] 內(nèi)的元素是可以舍去的，此時(shí)更新 right 到 mid - 1 的位置； 注意：這里找中間元素需要向上取整。 因?yàn)楹罄m(xù)移動(dòng)左右指針的時(shí)候： 左指針： left = mid ，可能會(huì)原地踏步（比如：如果向下取整的話，如果剩下 1,2 兩個(gè)元 素， left == 1， right == 2，mid == 1 。更新區(qū)間之后， left，right，mid 的值沒有改變，就會(huì)陷入死循環(huán)）。 右指針： right = mid - 1 ，是會(huì)向前移動(dòng)的，因此區(qū)間是會(huì)縮小的； ?綜上所述： 當(dāng)選擇兩段式的模板時(shí)： 在求 mid 的時(shí)候，只有 right - 1 的情況下，才會(huì)向上取整（也就是 +1 取中間數(shù)） ?山峰數(shù)組的峰頂 852. 山脈數(shù)組的峰頂索引 - 力扣（LeetCode） 暴力枚舉 峰頂?shù)奶攸c(diǎn)：?兩側(cè)的元素都要?。 因此，我們可以遍歷數(shù)組內(nèi)的每?個(gè)元素，找到某?個(gè)元素?兩邊的元素?即可。 class Solution { public: int peakIndexInMountainArray(vector int n = arr.size(); // 遍歷數(shù)組內(nèi)每?個(gè)元素，直到找到峰頂 for (int i = 1; i < n - 1; i++) // 峰頂滿?的條件 if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) return i; // 為了處理 oj 需要控制所有路徑都有返回值 return -1; } }; 二分查找 通過發(fā)現(xiàn)題目發(fā)現(xiàn)數(shù)據(jù)存在二段性，峰值左邊數(shù)值依次遞增，峰值右邊依次遞減。 算法思路： 峰頂數(shù)據(jù)特點(diǎn)： arr[i] > arr[i - 1] && arr[i] > arr[i + 1] ； 峰頂左邊的數(shù)據(jù)特點(diǎn)： arr[i] > arr[i - 1] && arr[i] < arr[i + 1] ，也就是呈現(xiàn)上升趨勢； 峰頂右邊數(shù)據(jù)的特點(diǎn)： arr[i] < arr[i - 1] && arr[i] > arr[i + 1] ，也就是呈現(xiàn)下降趨勢。 因此，根據(jù) mid 位置的信息，可以分為下?三種情況： 如果 mid 位置呈現(xiàn)上升趨勢，說明我們接下來要在 [mid + 1, right] 區(qū)間繼續(xù)搜索； 如果 mid 位置呈現(xiàn)下降趨勢，說明我們接下來要在 [left, mid - 1] 區(qū)間搜索； 如果 mid 位置就是?峰，直接返回結(jié)果。 因?yàn)榈谝粋€(gè)位置和最后一個(gè)位置不可能是峰值，所以left=1，right=arr.size()-2; class Solution { public: int peakIndexInMountainArray(vector { int left = 1, right = arr.size() - 2; while(left < right) { int mid = left + (right - left + 1) / 2; if(arr[mid] > arr[mid - 1]) left = mid; else right = mid - 1; } return left; } }; . 搜索旋轉(zhuǎn)排序數(shù)組中的最小值（medium） 153. 尋找旋轉(zhuǎn)排序數(shù)組中的最小值 - 力扣（LeetCode） ?暴力解法就是遍歷數(shù)據(jù)直接找最小值。當(dāng)然也可以直接sort排序，直接返回?cái)?shù)組首元素（哈哈哈，這個(gè)方法抽象） class Solution { public: int findMin(vector sort(nums.begin(),nums.end()); return nums[0]; } }; 二分查找 我們可以發(fā)現(xiàn)翻轉(zhuǎn)后的數(shù)組來兩段區(qū)間都是嚴(yán)格遞增的。 其中 C 點(diǎn)就是要求的點(diǎn)。 二分的本質(zhì)：找到一個(gè)判斷標(biāo)準(zhǔn)，使得查找區(qū)間能夠一分為二。 通過圖像我們可以發(fā)現(xiàn)， [A，B] 區(qū)間內(nèi)的點(diǎn)都是嚴(yán)格大于 D 點(diǎn)的值的， C 點(diǎn)的值是嚴(yán)格小 于 D 點(diǎn)的值的。但是當(dāng) [C，D] 區(qū)間只有一個(gè)元素的時(shí)候， C 點(diǎn)的值是可能等于 D 點(diǎn)的值 的。 因此，初始化左右兩個(gè)指針 left ， right ： 然后根據(jù) mid 的落點(diǎn)，我們可以這樣劃分下一次查詢的區(qū)間： 當(dāng) mid 在 [A，B] 區(qū)間的時(shí)候，也就是 mid 位置的值嚴(yán)格大于 D 點(diǎn)的值，下一次查詢區(qū)間在 [mid + 1，right] 上； 當(dāng) mid 在 [C，D] 區(qū)間的時(shí)候，也就是 mid 位置的值嚴(yán)格?于等于 D 點(diǎn)的值，下次 查詢區(qū)間在 [left，mid] 上。 當(dāng)區(qū)間長度變成 1 的時(shí)候，就是我們要找的結(jié)果。 class Solution { public: int findMin(vector int left=0,right=nums.size()-1; int x=nums[right]; while(left int mid=left+(right-left)/2; if(nums[mid]>x) left=mid+1; else right=mid; } return nums[left]; } }; 結(jié)束語 二分查找的講解就到此結(jié)束啦，各位，相信通過這些題目的講解大家對(duì)二分有了全新的認(rèn)識(shí)和理解，下個(gè)算法我們將學(xué)習(xí)前綴和，歡迎大家來指導(dǎo)交流。 最后感謝各位友友的支持?。?！ 柚子快報(bào)邀請(qǐng)碼778899分享：算法魅力-二分查找實(shí)戰(zhàn) 相關(guān)鏈接
本文內(nèi)容根據(jù)網(wǎng)絡(luò)資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點(diǎn)和立場。
轉(zhuǎn)載請(qǐng)注明，如有侵權(quán)，聯(lián)系刪除。
BOL外貿(mào)優(yōu)選站
