二分查找（搜索）的英文名是 Binary Search荷愕，直譯過來其實應(yīng)該叫二進制搜索衡怀，但這些都不重要，只要知道有這么個英文名就行安疗。
什么是二分查找
二分查找是一種在每次比較之后將查找空間一分為二的算法抛杨。每次需要查找集合中的索引或元素時，都應(yīng)該考慮二分查找荐类。如果集合是無序的怖现，我們需要在應(yīng)用二分查找之前先對其進行排序。
二分查找是計算機科學中最基本玉罐、最有用的算法之一屈嗤。 它描述了在有序集合中搜索特定值的過程。二分查找中使用的術(shù)語有：
- 目標 Target —— 你要查找的值
- 索引 Index —— 你要查找的當前位置
- 左吊输、右指示符 Left饶号，Right —— 我們用來維持查找空間的指標
- 中間指示符 Mid —— 我們用來應(yīng)用條件來確定我們應(yīng)該向左查找還是向右查找的索引
二分的本質(zhì)
我們平時所說的二分大多指數(shù)組的二分，因為數(shù)組可以隨機訪問嘛璧亚；
不過這種二分實在太狹義了讨韭，二分的本質(zhì)是將問題規(guī)闹牛縮小到一半癣蟋，因此二分和數(shù)據(jù)結(jié)構(gòu)沒有本質(zhì)關(guān)系透硝！
但不同的數(shù)據(jù)結(jié)構(gòu)卻給二分賦予了不同的色彩；
比如：
跳表就是鏈表的二分（比如redis的跳躍表）疯搅；
二叉搜索樹就是樹的二分濒生；
……；
二分查找的三個基本組成部分
二分查找的先決條件是【有序的折半邏輯】幔欧，即每次折半查詢時罪治，有條件區(qū)分出另一半數(shù)據(jù)，不一定非得是數(shù)學上的升序降序礁蔗；二分查找一般由三個主要部分組成：
- 預(yù)處理 —— 如果集合未排序觉义，則進行排序。
- 二分查找 —— 使用循環(huán)或遞歸在每次比較后將查找空間劃分為兩半浴井。
- 后處理 —— 在剩余空間中確定可行的候選者晒骇。
二分查找的三種基本模板
模板-I-1
- 一般用于精確查找值;
- 結(jié)束條件：L>R;
while ($L <= $R) {
$mid=$L+floor(($R-$L)/2);//防止溢出
if ($mid < $target) {
$L = $mid+1;
} else if ($mid > $target) {
$R = $mid-1;
} else if ($mid == $target) {
return $mid; //注意，此模板一般直接返回結(jié)果
}
}
return null;
模板-II-2
- 一般用于尋找左邊界磺浙；
- 結(jié)束條件：L==R洪囤；
while ($L < $R) {
$mid=$L+floor(($R-$L)/2);//防止溢出
if ($mid < $target) {
$L = $mid+1;
} else if ($mid >= $target) {
$R = $mid; //注意此處R=mid
}
}
return $R;//L或R都行，因為結(jié)束條件是L==R;
模板-III
int binarySearch(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left + 1 < right){
// Prevent (left + right) overflow
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid;
} else {
right = mid;
}
}
// Post-processing:
// End Condition: left + 1 == right
if(nums[left] == target) return left;
if(nums[right] == target) return right;
return -1;
}
模板 #3 是二分查找的另一種獨特形式：
它用于搜索需要訪問當前索引及其在數(shù)組中的直接左右鄰居索引的元素或條件撕氧。
模板-III 的邊界條件
- 初始條件：left = 0, right = length-1
- 終止：left + 1 == right
- 向左查找：right = mid
- 向右查找：left = mid
透過小白兔(鼠)試毒問題去看二分的本質(zhì)
盡管上面已經(jīng)說了, 不要將二分法局限于某種數(shù)據(jù)結(jié)構(gòu), 但多數(shù)人還是習慣于狹義的將二分法理解為數(shù)組的二分, 總覺著問題得能具象化為一組數(shù)才可以施展二分大法瘤缩。
實則不然, 上面提到過, 二分的本質(zhì)在于將問題規(guī)模縮小到原來的一半, 所以請看下面這道題：
現(xiàn)在有1000瓶藥水, 其中1瓶是毒藥, 只需一滴就可讓小白兔在24小時內(nèi)死亡; 問伦泥，如何在最短時間內(nèi)用最少的小白兔, 找出這瓶毒藥剥啤？
該題據(jù)說是某大(鵝)廠面試題, 看上去似乎挺簡單:
1000只小兔子, 挨個兒試; 或者, 1只兔子, 一天試一瓶;
不過嘛, 想想也知道答案不是這樣, 要不, 就沒有考你的必要了。
那么不脯，如何巧妙的找到這瓶毒藥呢府怯？
這就要用到本文一直在講的二分法了；乍一看跨新，這題貌似和二分扯不上關(guān)系富腊，如果我們把題目簡化一下，就好理解了域帐。
現(xiàn)在有4瓶藥水, 其中1瓶是毒藥, 只需一滴就可讓小白兔在24小時內(nèi)死亡; 問赘被，如何在最短時間內(nèi)用最少的小白兔, 找出這瓶毒藥？
先套用上面的簡單解法：4只小兔子肖揣，或者1只試4天民假；
發(fā)散你的小思維再想一想，能否再縮短一些龙优？
實際上羊异，這個簡單方案，用不到4只或4天，只需3只或3天即可野舶，因為最后一瓶可以用排除法得到答案易迹；
所以，問題就可以繼續(xù)簡化為：
現(xiàn)在有3瓶藥水, 毒藥可能在里邊也可能不在平道，如何用最小的代價確定它在不在里邊睹欲。
接下來該如何優(yōu)化這個解法呢，也就是一屋，如何把3瓶不相干的藥水二分呢窘疮？
如果你沒有思路，就想想二分法的英文名冀墨，它為什么叫 Binary Search闸衫？
其實就是將數(shù)字轉(zhuǎn)化為二進制吖！聰明的你是不是也想到了呢诽嘉？
現(xiàn)在我們將 1到3號瓶 按二進制進行編號：
01 - 1號瓶
10 - 2號瓶
11 - 3號瓶
它們的共性是什么蔚出，也就一目了然了，每一個數(shù)都由兩位二進制數(shù)構(gòu)成含懊，如果我們把問題分成這么兩類來看：
1身冬、有毒藥水的第1位是否為1；
2岔乔、有毒藥水的第2位是否為1酥筝；
是不是就可以借用二分思路了呢？
根據(jù)這個思路雏门，需要請來兩只小兔子奉獻一下嘿歌，將其編號為1號兔和2號兔，并將3瓶藥水按上面的二進制表達式編號：
1號兔只喂二進制第一位是1的藥水茁影；
2號兔只喂二進制第二位是1的藥水宙帝；
24小時后，如果：
1號兔死亡募闲，說明有毒的是3瓶中的第1瓶步脓；
2號兔死亡，說明有毒的是3瓶中的第2瓶浩螺；
如果1號和2號都沒事兒靴患，說明有毒的是被我們拋棄的那一瓶；為了便于統(tǒng)一觀察要出，可以將被拋棄的那瓶藥水的二進制編號為 00鸳君，轉(zhuǎn)換為十進制即第0號瓶：
01 - 1號瓶
10 - 2號瓶
11 - 3號瓶
00 - 0號(4號)瓶
如此二分優(yōu)化下來，4瓶藥水患蹂，我們只需2只小兔子奉獻或颊，就可在1天內(nèi)找出有毒藥水砸紊；
下面我們把瓶子數(shù)量：
擴展到100瓶；套用二進制思路囱挑，只需7只就可在1天內(nèi)找出有毒藥水醉顽；
再擴展到1000瓶，只需10只就可在1天內(nèi)找出有毒藥水看铆；
聰明的你想到答案了嗎徽鼎？看完這道題盛末，你是否對二分法有了更深入的了解呢弹惦？
提示：
99的二進制表達式為：1100011；
999的二進制表達式為：1111100111；
嚴格來說，原題中的1000瓶解題思路并非是二分法幽邓，稱之為十分法更為貼切（100瓶則應(yīng)稱之為七分法）眼滤，但本質(zhì)都是套用了二分法的思路，將問題規(guī)睦愦龋縮小到原來的十分之一；
