二分查找（搜索）的英文名是 Binary Search，直譯過來其實(shí)應(yīng)該叫二進(jìn)制搜索，但這些都不重要，只要知道有這么個(gè)英文名就行。

什么是二分查找

二分查找是一種在每次比較之后將查找空間一分為二的算法。每次需要查找集合中的索引或元素時(shí)，都應(yīng)該考慮二分查找。如果集合是無序的，我們需要在應(yīng)用二分查找之前先對其進(jìn)行排序。
二分查找是計(jì)算機(jī)科學(xué)中最基本、最有用的算法之一。 它描述了在有序集合中搜索特定值的過程。二分查找中使用的術(shù)語有：

• 目標(biāo) Target —— 你要查找的值
• 索引 Index —— 你要查找的當(dāng)前位置
• 左、右指示符 Left，Right —— 我們用來維持查找空間的指標(biāo)
• 中間指示符 Mid —— 我們用來應(yīng)用條件來確定我們應(yīng)該向左查找還是向右查找的索引

二分的本質(zhì)

我們平時(shí)所說的二分大多指數(shù)組的二分，因?yàn)閿?shù)組可以隨機(jī)訪問嘛；
不過這種二分實(shí)在太狹義了，二分的本質(zhì)是將問題規(guī)?？s小到一半，因此二分和數(shù)據(jù)結(jié)構(gòu)沒有本質(zhì)關(guān)系！
但不同的數(shù)據(jù)結(jié)構(gòu)卻給二分賦予了不同的色彩；
比如：

跳表就是鏈表的二分（比如redis的跳躍表）；
二叉搜索樹就是樹的二分；
……；

二分查找的三個(gè)基本組成部分

二分查找的先決條件是【有序的折半邏輯】，即每次折半查詢時(shí)，有條件區(qū)分出另一半數(shù)據(jù)，不一定非得是數(shù)學(xué)上的升序降序；二分查找一般由三個(gè)主要部分組成：

• 預(yù)處理 —— 如果集合未排序，則進(jìn)行排序。
• 二分查找 —— 使用循環(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都行，因?yàn)榻Y(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 是二分查找的另一種獨(dú)特形式：
它用于搜索需要訪問當(dāng)前索引及其在數(shù)組中的直接左右鄰居索引的元素或條件。

模板-III 的邊界條件

• 初始條件：left = 0, right = length-1
• 終止：left + 1 == right
• 向左查找：right = mid
• 向右查找：left = mid

透過小白兔(鼠)試毒問題去看二分的本質(zhì)

盡管上面已經(jīng)說了, 不要將二分法局限于某種數(shù)據(jù)結(jié)構(gòu), 但多數(shù)人還是習(xí)慣于狹義的將二分法理解為數(shù)組的二分, 總覺著問題得能具象化為一組數(shù)才可以施展二分大法。
實(shí)則不然, 上面提到過, 二分的本質(zhì)在于將問題規(guī)?？s小到原來的一半, 所以請看下面這道題：

現(xiàn)在有1000瓶藥水, 其中1瓶是毒藥, 只需一滴就可讓小白兔在24小時(shí)內(nèi)死亡; 問，如何在最短時(shí)間內(nèi)用最少的小白兔, 找出這瓶毒藥？

該題據(jù)說是某大(鵝)廠面試題, 看上去似乎挺簡單:
1000只小兔子, 挨個(gè)兒試; 或者, 1只兔子, 一天試一瓶;

不過嘛, 想想也知道答案不是這樣, 要不, 就沒有考你的必要了。
那么，如何巧妙的找到這瓶毒藥呢？
這就要用到本文一直在講的二分法了；乍一看，這題貌似和二分扯不上關(guān)系，如果我們把題目簡化一下，就好理解了。

現(xiàn)在有4瓶藥水, 其中1瓶是毒藥, 只需一滴就可讓小白兔在24小時(shí)內(nèi)死亡; 問，如何在最短時(shí)間內(nèi)用最少的小白兔, 找出這瓶毒藥？

先套用上面的簡單解法：4只小兔子，或者1只試4天；
發(fā)散你的小思維再想一想，能否再縮短一些？
實(shí)際上，這個(gè)簡單方案，用不到4只或4天，只需3只或3天即可，因?yàn)樽詈笠黄靠梢杂门懦ǖ玫酱鸢福?br> 所以，問題就可以繼續(xù)簡化為：

現(xiàn)在有3瓶藥水, 毒藥可能在里邊也可能不在，如何用最小的代價(jià)確定它在不在里邊。

接下來該如何優(yōu)化這個(gè)解法呢，也就是，如何把3瓶不相干的藥水二分呢？
如果你沒有思路，就想想二分法的英文名，它為什么叫 Binary Search？
其實(shí)就是將數(shù)字轉(zhuǎn)化為二進(jìn)制吖！聰明的你是不是也想到了呢？

現(xiàn)在我們將 1到3號瓶 按二進(jìn)制進(jìn)行編號：

01 - 1號瓶
10 - 2號瓶
11 - 3號瓶

它們的共性是什么，也就一目了然了，每一個(gè)數(shù)都由兩位二進(jìn)制數(shù)構(gòu)成，如果我們把問題分成這么兩類來看：

1、有毒藥水的第1位是否為1；
2、有毒藥水的第2位是否為1；

是不是就可以借用二分思路了呢？

根據(jù)這個(gè)思路，需要請來兩只小兔子奉獻(xiàn)一下，將其編號為1號兔和2號兔，并將3瓶藥水按上面的二進(jìn)制表達(dá)式編號：

1號兔只喂二進(jìn)制第一位是1的藥水；
2號兔只喂二進(jìn)制第二位是1的藥水；

24小時(shí)后，如果：
1號兔死亡，說明有毒的是3瓶中的第1瓶；
2號兔死亡，說明有毒的是3瓶中的第2瓶；

如果1號和2號都沒事兒，說明有毒的是被我們拋棄的那一瓶；為了便于統(tǒng)一觀察，可以將被拋棄的那瓶藥水的二進(jìn)制編號為 00，轉(zhuǎn)換為十進(jìn)制即第0號瓶：

01 - 1號瓶
10 - 2號瓶
11 - 3號瓶
00 - 0號(4號)瓶

如此二分優(yōu)化下來，4瓶藥水，我們只需2只小兔子奉獻(xiàn)，就可在1天內(nèi)找出有毒藥水；

下面我們把瓶子數(shù)量：
擴(kuò)展到100瓶；套用二進(jìn)制思路，只需7只就可在1天內(nèi)找出有毒藥水；
再擴(kuò)展到1000瓶，只需10只就可在1天內(nèi)找出有毒藥水；
聰明的你想到答案了嗎？看完這道題，你是否對二分法有了更深入的了解呢？

_{提示：
99的二進(jìn)制表達(dá)式為：1100011；
999的二進(jìn)制表達(dá)式為：1111100111；
嚴(yán)格來說，原題中的1000瓶解題思路并非是二分法，稱之為十分法更為貼切（100瓶則應(yīng)稱之為七分法），但本質(zhì)都是套用了二分法的思路，將問題規(guī)模縮小到原來的十分之一；}