二分查找也叫作折半查找。二分查找有兩個(gè)要求榕吼，一個(gè)是數(shù)列有序，另一個(gè)是數(shù)列使用順序存儲(chǔ)結(jié)構(gòu)勉失。他的思想很簡(jiǎn)單羹蚣，但是在書(shū)寫(xiě)過(guò)程中如果邊界條件無(wú)法正確的確定，很容易陷入到循環(huán)中無(wú)法跳出乱凿。

二段性

二段性是集合中的元素有存在分界線(xiàn)顽素，給定條件可以將集合中元素分為兩部分，一部分滿(mǎn)足條件徒蟆，一部分不滿(mǎn)足條件胁出。

1. 分界線(xiàn)之前的第一個(gè)元素，也就是最后一個(gè)滿(mǎn)足條件的值后专，我們稱(chēng)為ML(Meeting Condition Last)
2. 分界線(xiàn)之后的第一個(gè)元素划鸽，也就是第一個(gè)不滿(mǎn)足該條件的值，我們稱(chēng)為NB(Not Meeting Condition Begining)

區(qū)間問(wèn)題

此節(jié)主要講二分查找的細(xì)節(jié)處理戚哎，如果要看二分的查找過(guò)程不建議看這篇裸诽，文中所講的二分偽代碼為：

l = -1,r = N + 1
while l + 1 != r
    m = l + (r - l >> 1)
    if judge(m) // 根據(jù)題目修改judge
        l = m
    else
        r = m
return l/r // 最終返回時(shí)根據(jù)需求進(jìn)行返回

對(duì)于一個(gè)給定的數(shù)組進(jìn)行二分查找時(shí)，需考慮以下步驟

1. 確定左右邊界：這里確定左右邊界分別為和型凳。

面對(duì)查找小于的最后一個(gè)數(shù)時(shí)丈冬，如果令左邊界的值為，那么左邊界的初始條件已經(jīng)不滿(mǎn)足問(wèn)題要求了甘畅，因此采用0作為一個(gè)通用的二分求解方法的左邊界并不是一個(gè)合理的方案埂蕊。

同理，面對(duì)查找大于的第一個(gè)數(shù)疏唾，也不可以令右邊界的值為1蓄氧。

2. 獲得中點(diǎn)：使用作為獲得重點(diǎn)的公式。

采用其他的公式槐脏，比如喉童，也是可以的，但是為了防止與相加導(dǎo)致的數(shù)值溢出使用上面的公式顿天。

3. 收縮區(qū)間：使用和作為收縮區(qū)間的公式堂氯。

為了避免寫(xiě)出死循環(huán)，必須保證每次進(jìn)入之后牌废，可行區(qū)間都在變小咽白，且最終推出循環(huán)。在此先引出程序終止的條件為鸟缕，當(dāng)面對(duì)晶框，此時(shí)以滿(mǎn)足終止條件所以無(wú)論和取多少，都會(huì)退出循環(huán)；當(dāng)面對(duì)三妈，中點(diǎn)為畜埋，此時(shí)循環(huán)體內(nèi)的收縮公式會(huì)將賦值給或者，再此達(dá)到終止條件畴蒲，退出循環(huán)悠鞍；當(dāng)面對(duì)，按照里的分析模燥，其最終會(huì)進(jìn)入到或者的條件咖祭。

4. 確定終止條件：這里終止條件為，即循環(huán)條件為蔫骂。

因?yàn)榈哪繕?biāo)時(shí)遍歷整個(gè)數(shù)組么翰，因此終止條件要確保所有的元素都可以被包含在內(nèi)。同上面的收縮區(qū)間的公式相配合可以構(gòu)成一個(gè)二分查找辽旋。

5. 和的指向問(wèn)題

和的指向哪個(gè)數(shù)值浩嫌，最終還是取決于judge條件。對(duì)于我們要查找小于零第一個(gè)數(shù)补胚，其judge條件為码耐，，溶其。

對(duì)于一個(gè)例子：

1. 找到小于的最后一個(gè)數(shù)：

   class Solution {
       public int binarySearch(int[] arr, int t) {
           int l = -1, r = arr.length;
           while (l + 1 != r) {
               int m = l + (r - l >> 1);
               if (arr[m] < t) l = m; // judge條件：如果小于t骚腥，則讓l=m；否則r=m
               else r = m;
           }
           return l; // 返回l
       }
   }
   
   Solution solution = new Solution();
   System.out.println(solution.binarySearch(new int[]{1, 2, 3, 5, 5, 5, 8, 9}, 5)); // 返回2瓶逃，對(duì)應(yīng)的值為3
   

2. 找到小于等于的最后一個(gè)數(shù)：

   class Solution {
       public int binarySearch(int[] arr, int t) {
           int l = -1, r = arr.length;
           while (l + 1 != r) {
               int m = l + (r - l >> 1);
               if (arr[m] <= t) l = m; // judge條件：如果小于等于t束铭，則讓l=m；否則r=m
               else r = m;
           }
           return l; // 返回l
       }
   }
   
   Solution solution = new Solution();
   System.out.println(solution.binarySearch(new int[]{1, 2, 3, 5, 5, 5, 8, 9}, 5)); // 返回5厢绝，對(duì)應(yīng)的值為5
   

3. 找到大于的第一個(gè)數(shù)：（判斷條件等價(jià)于找到小于等于的最后一個(gè)數(shù)）

   class Solution {
       public int binarySearch(int[] arr, int t) {
           int l = -1, r = arr.length;
           while (l + 1 != r) {
               int m = l + (r - l >> 1);
               if (arr[m] <= t) l = m; // judge條件：如果小于等于t契沫，則讓l=m；否則r=m
               else r = m;
           }
           return r; // 返回r
       }
   }
   
   Solution solution = new Solution();
   System.out.println(solution.binarySearch(new int[]{1, 2, 3, 5, 5, 5, 8, 9}, 5)); // 返回6昔汉，對(duì)應(yīng)的值為8
   

4. 找到大于等于的第一個(gè)數(shù)：（判斷條件等價(jià)于找到小于等于的最后一個(gè)數(shù)）

   class Solution {
       public int binarySearch(int[] arr, int t) {
           int l = -1, r = arr.length;
           while (l + 1 != r) {
               int m = l + (r - l >> 1);
               if (arr[m] < t) l = m; // judge條件：如果小于t懈万，則讓l=m；否則r=m
               else r = m;
           }
           return r; // 返回r
       }
   }
   
   Solution solution = new Solution();
   System.out.println(solution.binarySearch(new int[]{1, 2, 3, 5, 5, 5, 8, 9}, 5)); // 返回3挤庇，對(duì)應(yīng)的值為5 
   

參考文獻(xiàn)：

1. 二分查找為什么總是寫(xiě)錯(cuò)？
2. 二分法的邊界問(wèn)題詳細(xì)分析