柚子快報邀請碼778899分享：【算法】C++中的二分查找
柚子快報邀請碼778899分享：【算法】C++中的二分查找
?博客主頁：https://blog.csdn.net/2301_779549673 ?歡迎點贊 ? 收藏 ?留言 ? 如有錯誤敬請指正！ ?本文由 JohnKi 原創(chuàng)，首發(fā)于 CSDN? ?未來很長，值得我們?nèi)Ρ几案篮玫纳?
文章目錄
?前言????二分查找的實現(xiàn)方式????1. 樸素的二分模板????2. 查找左端點的二分模板????3. 查找右端點的二分模板?總結(jié)
?前言
二分查找，也被稱為折半查找，是一種在有序數(shù)組中高效查找目標(biāo)元素的算法。它的基本思想是將待查找的區(qū)間不斷地折半，通過比較中間元素與目標(biāo)元素的大小關(guān)系，逐步縮小查找范圍，直到找到目標(biāo)元素或者確定目標(biāo)元素不存在于數(shù)組中。
二分查找的優(yōu)點在于其查找速度較快。在有序數(shù)組中，對于長度為 n 的數(shù)組，二分查找的時間復(fù)雜度為 O (log n)。相比之下，線性查找的時間復(fù)雜度為 O (n)。例如，在一個包含 1024 個元素的有序數(shù)組中，線性查找最壞情況下可能需要進(jìn)行 1024 次比較，而二分查找最多只需要進(jìn)行 10 次比較（log?1024 = 10）。
????二分查找的實現(xiàn)方式
在二分查找中，二段性是一個非常重要的概念。
二段性指的是對于一個有序數(shù)組，存在一種性質(zhì)，使得數(shù)組可以被劃分為兩個區(qū)間，滿足在其中一個區(qū)間中性質(zhì)成立，在另一個區(qū)間中性質(zhì)不成立。
例如，對于一個升序排列的整數(shù)數(shù)組，要查找某個特定的整數(shù) target。如果當(dāng)前數(shù)組中的某個元素大于等于 target，那么可以認(rèn)為這個元素以及它右邊的部分處于一個區(qū)間，這個區(qū)間中的元素都大于等于 target；而這個元素左邊的部分處于另一個區(qū)間，這個區(qū)間中的元素都小于 target。這就體現(xiàn)了二段性。
根據(jù)數(shù)學(xué)演算，每次取最中值的二分查找算法是時間復(fù)雜度最均勻和最好的，這在算法導(dǎo)論中有證明，但是太復(fù)雜了，就不在這說了
1. 確定查找方向
在二分查找過程中，通過判斷當(dāng)前中間元素與目標(biāo)元素的大小關(guān)系，可以確定目標(biāo)元素位于哪一個區(qū)間。如果中間元素小于目標(biāo)元素，說明目標(biāo)元素在中間元素右側(cè)的區(qū)間；如果中間元素大于目標(biāo)元素，說明目標(biāo)元素在中間元素左側(cè)的區(qū)間。
2. 縮小查找范圍
利用二段性，可以不斷地將查找范圍縮小一半。每次判斷都能排除掉一半的區(qū)間，從而大大提高查找效率。例如，在一個有 100 個元素的有序數(shù)組中，使用二分查找最多只需要進(jìn)行 7 次比較就可以找到目標(biāo)元素，而如果采用順序查找可能需要最多 100 次比較。
????1. 樸素的二分模板
樸素的二分查找模板的查找效率其實可以說是最高的，因為它一旦遇到準(zhǔn)確的值就會直接退出，但是這也為其添加了局限性，如果數(shù)組不存在指定值，或者需要查找的是一個區(qū)間的左值 or 右值，那么就很難實現(xiàn)
以題為例 鏈接: 704. 二分查找
這道題就可以用樸素二分查找來做，
設(shè)置循環(huán)條件：left <= rightmid = left + ((right - left) >> 1) : 查中間值(偶數(shù)時取左值)，并設(shè)置防溢出設(shè)置 大于 小于 等于 的情況一旦 等于 返回值循環(huán)結(jié)束未找到，返回 -1
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] < target) left = mid + 1;
else if(nums[mid] > target) right = mid -1;
else return mid;
}
return -1;
}
};
樸素二分模板總結(jié)
????2. 查找左端點的二分模板
查找最左值時可以參考上圖，我們需要找到一個值使其左邊都是小于要查找的值的，右邊包括其本身都是要大于等于要查找的值的，因此我們假設(shè) [0, left) [right, end]為兩個分區(qū)，那么我們就可以認(rèn)為
1. 退出循環(huán)的值為 left < right
再然后我們因為要查找的值 如果 t >= nums[right] 那么代表他必然屬于右邊這個區(qū)間，因此，我們在設(shè)置 right 更新時，不能使其 right = mid - 1，而是
2. if(… >= …) right = mid
同理我們推導(dǎo)left，left 的最終所處位置其實應(yīng)該和 right 一樣，因為它往左的所有元素都是小于 t 的，因而 left 更新時
3. else left = mid + 1
最后我們需要確保循環(huán)不會一直下去，這就我們需要確保，當(dāng) left + 1 == right 時我們所查找的 mid 值。如果查右邊，那么將一直進(jìn)行 if(… >= …) right = mid 導(dǎo)致陷入死循環(huán)，所以
4. mid = left + ((right - left) >> 1))
最左值二分模板總結(jié)
????3. 查找右端點的二分模板
最右值其實和最左值的理解差不多，就是有 等于 的時候，left 不用超過mid，right 變成 mid - 1。
還有一個重要的點是，mid 的確定，因為 當(dāng) left + 1 == right 時我們所查找的 mid 值 為左值時，就會一直 if(… <= …) left = mid 陷入死循環(huán)，所以 mid = left + ((right - left + 1) >> 1))
最右值二分模板總結(jié)
以題為例 鏈接: 34. 在排序數(shù)組中查找元素的第一個和最后一個位置 - 同時解決左端點右端點問題 具體流程完完全全就是左右端點的模板，就不逐條解釋了
vector
int left = 0, right = nums.size() - 1;
vector
// 防止傳入vector為空
if (nums.empty())
return ret;
// 找左端點
while (left < right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] < target)
left = mid + 1;
else
right = mid;
}
if (nums[right] == target)
ret[0] = right;
right = nums.size() - 1;
// 找右端點
while (left < right) {
int mid = left + ((right - left + 1) >> 1);
if (nums[mid] > target)
right = mid - 1;
else
left = mid;
}
if (nums[left] == target)
ret[1] = left;
return ret;
}
?總結(jié)
本篇博文對 【算法】C++中的二分查找 做了一個較為詳細(xì)的介紹，不知道對你有沒有幫助呢
覺得博主寫得還不錯的三連支持下吧！會繼續(xù)努力的~
柚子快報邀請碼778899分享：【算法】C++中的二分查找
精彩內(nèi)容
本文內(nèi)容根據(jù)網(wǎng)絡(luò)資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點和立場。
轉(zhuǎn)載請注明，如有侵權(quán)，聯(lián)系刪除。
Paytmmall跨境支付購
