1.概念

如果想要在數(shù)組中查找一個(gè)數(shù)，最基本的方法就是暴力解法：一次遍歷，這時(shí)候時(shí)間復(fù)雜度是O(N),二分查找就是其中的一種優(yōu)化，時(shí)間復(fù)雜度是O(logN);具體做法是一步一步逼近直到找到。前提是數(shù)組需要是一個(gè)排序數(shù)組。

定義：二分查找也稱折半查找（Binary Search），是一種在有序數(shù)組中查找某一特定元素的搜索算法。我們可以從定義可知，運(yùn)用二分搜索的前提是數(shù)組必須是有序的，這里需要注意的是，我們的輸入不一定是數(shù)組，也可以是數(shù)組中某一區(qū)間的起始位置和終止位置

2.過程

1.二分查找先初始化一個(gè)搜索空間，然后再這個(gè)搜索空間上去尋找某個(gè)值，注意這個(gè)搜索空間是有某種規(guī)律，比如說是有序的；

2.因?yàn)檫@種規(guī)律，直接去看中間值，如果判斷中間值和我們想要的結(jié)果的關(guān)系，比如搜索數(shù)字，看中間值和目標(biāo)值的大小關(guān)系；

3.如果mid>t,那證明應(yīng)該去前半部分搜索；如果mid<t,那說明該去前半部分搜索；

4.然后接著在新的搜索空間執(zhí)行2，3；

關(guān)鍵

Knuth 大佬（發(fā)明 KMP 算法的那位）怎么說的：

Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky...

思路很簡單，細(xì)節(jié)是魔鬼；

3.模板

上述功能就是如果能在數(shù)組中找到目標(biāo)值，就返回其索引，如果找不到，就返回其下標(biāo)；如果目標(biāo)值比中間值還大，那肯定在中間值右側(cè)(因?yàn)閿?shù)組已經(jīng)排序好了)，如果目標(biāo)值比mid值小，那肯定在mid左側(cè)。

細(xì)節(jié)1：為什么while循環(huán)的條件時(shí)<=?

因?yàn)槲覀兂跏蓟臅r(shí)候右側(cè)區(qū)間是nums.length-1;所以是包括right的，即我們的區(qū)間是[left,right],這樣一個(gè)左閉右閉的區(qū)間，把這個(gè)區(qū)間理解成搜索區(qū)間，即我們是在這樣一個(gè)區(qū)間上搜索，那什么時(shí)候停止呢，兩個(gè)原因：

1.找到了目標(biāo)值，那就停止；

2.沒找到目標(biāo)值，但是搜索區(qū)間為空了，沒得找了，這時(shí)候停止；

所以在最后一個(gè)=的時(shí)候，比如[2,2]這時(shí)候區(qū)間還不為空，萬一就是這個(gè)2呢。

細(xì)節(jié)2：為什么寫成left+((right-left) >> 1);

這主要是為了防止溢出，記住就可以了，注意除以2,用位運(yùn)算的話會比較快一點(diǎn)，而且記得帶外面那個(gè)大括號；

細(xì)節(jié)3： 為什么left = mid + 1，right = mid - 1？

想一下剛才搜索區(qū)間的概念，如果發(fā)現(xiàn)了索引mid不是要找的target，那自然要從將mid剔除掉，從mid的左邊或者右邊找起來了。

缺陷：上述算法存在一個(gè)缺陷就是不能返回左右側(cè)邊界，比如數(shù)組是[1,2,2,2,3], target是2，這時(shí)候返回的索引是2，沒有辦法返回左右邊界。

4.樣例

34. 在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置

33. 搜索旋轉(zhuǎn)排序數(shù)組

劍指 Offer 53 - II. 0～n-1中缺失的數(shù)字

仔細(xì)體會上面3個(gè)樣例。

1.解決了上面說到的不能返回左右邊界的問題；

2.這個(gè)問題是不完全有序數(shù)組的二分查找；基本思路就是將其往排序數(shù)組上趕，比較mid和left來確定是前半段有序還是后半段有序；

3.是二分查找的一個(gè)問題，并不僅僅是查找某個(gè)值某個(gè)元素，重點(diǎn)去感受最后的left=right=mid；體會最后跳出循環(huán)的返回值；

5.體會

當(dāng)寫成這樣時(shí)：返回的left是第一個(gè)>=target的值的索引。

如果原數(shù)組有target返回的就是第一個(gè)target的索引；

如果沒有那就是第一個(gè)比target大的值的索引(或者可以理解為要將target插入的位置索引)；

之所以有上面的結(jié)論就在于最后一步一定是left=right=mid，而且mid左側(cè)都<t,mid右側(cè)都>=t,這時(shí)候執(zhí)行判斷，如果mid大于等于target，那就返回它了，也就是left，如果<target,那就執(zhí)行l(wèi)eft+1，返回的就是第一個(gè)>=target的值；

注意查看上面中提到的二分法的模板和細(xì)節(jié)，注意什么時(shí)候帶等號，什么時(shí)候不帶等號；

二分查找本質(zhì)上就是一個(gè)不斷縮小搜索空間的過程，比如我們找出某個(gè)值，就是在不斷的把空間縮??；找出哪個(gè)數(shù)字亂序，也在不斷的把空間縮?。磺笠粋€(gè)數(shù)的開根號，不斷的縮小空間然后拿值去逼近。這個(gè)過程要多想一下，就是我們不斷的縮小空間，然后每次都是拿這個(gè)空間上的中間值去做某種判斷，然后去逼近我們的結(jié)果。

二分查找應(yīng)用的前提就是一定是一個(gè)有序的，或者半有序的，如果是半有序的話原則是就是不斷向有序上去趕，因?yàn)橹挥性谟行虻臅r(shí)候才能去二分；

上面提供的二分查找的模板要始終明白在最后一步跳出循環(huán)前兩點(diǎn)：

1.最后一步一定是right=left=mid。

2.mid左側(cè)和右側(cè)一定是已經(jīng)有了規(guī)律的了。比如查找值的時(shí)候，mid左側(cè)都比t值小，mid右側(cè)都比t值大；比如判斷從哪個(gè)數(shù)字開始亂了，mid左側(cè)一定是整齊的，mid右側(cè)一定是亂的。那這時(shí)候只要去判斷一下mid的值就可以了。如果mid>t或者說mid亂了，那正好返回left也就是mid，如果mid<t或者說mid沒亂，那left=mid+1，這不就正好是第一個(gè)大于t或者第一個(gè)亂的了嗎。

另外，對現(xiàn)在我們的大多數(shù)朋友來說還是學(xué)編程技術(shù)最重要！栽一棵樹最好的時(shí)間是十年前，其次是現(xiàn)在。對于準(zhǔn)備學(xué)習(xí)編程的小伙伴，如果你想更好的提升你的編程核心能力（內(nèi)功）不妨從現(xiàn)在開始！

微信公眾號：C語言編程學(xué)習(xí)基地

整理分享（多年學(xué)習(xí)的源碼、項(xiàng)目實(shí)戰(zhàn)視頻、項(xiàng)目筆記，基礎(chǔ)入門教程）

歡迎轉(zhuǎn)行和學(xué)習(xí)編程的伙伴，利用更多的資料學(xué)習(xí)成長比自己琢磨更快哦！