簡單思路：
當(dāng)我們要從一個(gè)序列中查找一個(gè)元素的時(shí)候，最快想到的方法就是順序查找法（即：從前到后依次查找）。但這種方法過于無腦，就是暴力的把每個(gè)元素都排查一遍。元素個(gè)數(shù)少的時(shí)候還行，一旦元素個(gè)數(shù)多起來，效率是非常低下，所以在實(shí)際中這種查找的方法是被摒棄的。
當(dāng)題目或者實(shí)際對(duì)時(shí)間復(fù)雜度有著很高的要求的時(shí)候，這種暴力解法就顯得很乏力
這里就不得不介紹一種簡單且效率較高的查找方法了：二分查找法，又稱折半查找法。但該方法是建立在有序的前提下的，基本思路就是：
利用兩個(gè)指針left和right，不斷取中點(diǎn)來不斷把區(qū)間減小從而找到我們的答案
二分查找法的優(yōu)勢：
-
二分查找法的時(shí)間復(fù)雜度：O（logN）
-
暴力解法的時(shí)間復(fù)雜度：O（N）
如何直觀來體現(xiàn)二分查找法時(shí)間復(fù)雜度的優(yōu)勢呢？
可以看出 二分查找 在查找數(shù)字 37 時(shí)只需3次，而 順序查找 在查找37時(shí)需要12次。
二分查找的條件：
很多算法書都是寫的具有有序性，其實(shí)更準(zhǔn)確的是具有二段性
- 也就是具有可以把數(shù)組分為兩端的性質(zhì)
二分查找有兩個(gè)限制條件：
- 查找的數(shù)量只能是一個(gè)，不能是多個(gè)
- 查找的對(duì)象在邏輯上必須是有序的（這個(gè)不是必要條件，更深層次是就有二段性）
樸素二分查找：
1.left=0，right=數(shù)組最后一個(gè)位置的下標(biāo)
2.取中點(diǎn)：mid=（right-left）/2
二分法的思想很簡單，因?yàn)檎麄€(gè)數(shù)組是有序的，數(shù)組默認(rèn)是遞增的。
首先選擇數(shù)組中間的數(shù)字和需要查找的目標(biāo)值比較
-
如果相等最好，就可以直接返回答案了
-
如果不相等
如果中間的數(shù)字大于目標(biāo)值，則中間數(shù)字向右的所有數(shù)字都大于目標(biāo)值，全部排除
如果中間的數(shù)字小于目標(biāo)值，則中間數(shù)字向左的所有數(shù)字都小于目標(biāo)值，全部排除
704. 二分查找
以此題為例：
class Solution {
public:
int search(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) return mid;
if(nums[mid]>target) right=mid-1;
if(nums[mid]<target) left=mid+1;
}
return -1;
}
};
樸素二分查找的模版：
while(left<=right)
{
int mid=left+(right-left)/2;
if(nums[mid]==target) return mid;
if(nums[mid]>target) ...;
if(nums[mid]<target) ...;
}
return ...;
二分查找左右端點(diǎn)：
我們通過一個(gè)例子：
34. 在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置
本題我們利用二分來解決左右端點(diǎn)的問題，首先left和right肯定有的
我們通過一個(gè)示例來了解本題:[1,2,3,3,3,4,5]
查找左端點(diǎn)：我們這里用t來代替target（這樣比較好敘述）
- 二分的思路操作：我們可以將上述示例分為兩個(gè)部分，因?yàn)槲覀儸F(xiàn)在查找左端點(diǎn)，因此我可以將示例分為【[1,2],[3,3,3,4,5]】
- 當(dāng)x<t時(shí),處于【1,2】這個(gè)區(qū)間，left=mid+1
- 當(dāng)x>=t時(shí)，處于【3,3,3,4,5】這個(gè)區(qū)間，right=mid（這里不能等于mid-1，因?yàn)槿绻鹠id=0，right=-1會(huì)越界）
- 細(xì)節(jié)處理：
循環(huán)條件：
- left<right √
- left<=right ×
我們選擇那種呢？我們來討論一下：
- 有結(jié)果
- 全大于t（t1），right一直向左走，最后right為left結(jié)束，如果是left<=right會(huì)死循環(huán)
- 全小于t（t2），left一直向右走，最后left在right右邊結(jié)束
以此我們只能選擇第一種不能選擇第二種！
求中間的操作：
- left+(right-left)/2 ×
- left+(right-left+1)/2 √
我們考慮一下極端情況就可以知道了！當(dāng)只剩下兩個(gè)元素的時(shí)候：
第一種沒有問題，第二種mid=0+2/2=1，當(dāng)進(jìn)行l(wèi)eft+1操作的時(shí)候會(huì)發(fā)生越界
查找右端點(diǎn)
- 二分的思路操作：我們可以將上述示例分為兩個(gè)部分，因?yàn)槲覀儸F(xiàn)在查找左端點(diǎn)，因此我可以將示例分為【[1,2,3,3,3].[4,5]】
- 當(dāng)x<=t時(shí),處于【1,2,3,3,3】這個(gè)區(qū)間，left=mid
- 當(dāng)x>t時(shí)，處于【4,5】這個(gè)區(qū)間，right=mid-1
- 細(xì)節(jié)處理：
循環(huán)條件：
- left<right √
- left<=right ×
還是選擇left<right
求中間的操作：
- left+(right-left)/2 √
- left+(right-left+1)/2 ×
我們考慮一下極端情況就可以知道了！當(dāng)只剩下兩個(gè)元素的時(shí)候：
第一種當(dāng)mid=0+1/2=0時(shí)，right=mid-1越界，第二種沒有問題
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
//特殊情況處理一下
if(nums.size()==0)return {-1,-1};
int left=0,right=nums.size()-1;
vector<int> ret;
//查找左端點(diǎn)
while(left<right)
{
int mid=left+(right-left)/2;
if(nums[mid]<target)left=mid+1;
if(nums[mid]>=target)right=mid;
}
//當(dāng)left==right時(shí)就是結(jié)果
if(nums[left]!=target)return {-1,-1};
else ret.push_back(left);
//查找右端點(diǎn)
left=0,right=nums.size()-1;
while(left<right)
{
int mid=left+(right-left+1)/2;
if(nums[mid]<=target)left=mid;
if(nums[mid]>target)right=mid-1;
}
if(nums[right]!=target)return {-1,-1};
else ret.push_back(right);
return ret;
}
};
查找區(qū)間左右端點(diǎn)的模版：
模版，這里主要是取中間這里不太一樣，左端點(diǎn)時(shí)不用+1，右端點(diǎn)+1（記憶當(dāng)下面出現(xiàn)-1，上面就+1）
至于left和right可以現(xiàn)場推導(dǎo)文章來源：http://www.zghlxwxcb.cn/news/detail-714384.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-714384.html
到了這里，關(guān)于【算法小課堂】二分查找算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
