點擊我跳轉末尾 獲取 粉絲專屬 《演算法和資料結構》原始碼，以及獲取博主的聯系方式，

前言

??二分查找，又叫二分列舉是在一個單調有序的陣列中查找某個元素的搜索演算法，原理比較簡單，基本說一遍就知道是怎么一回事，然而，實際程序中，很容易寫錯，比如：
??1）左區間是加一還是不加？
??2）右區間是減一還是不減？
??3）迭代的終止條件怎么寫？
??4）為什么有時候會死回圈？
??帶著以上幾個疑問，這篇文章將對二分查找的所有寫法進行一個歸納總結，

文章目錄

前言
一、線性列舉
- 1、線性列舉定義
- 2、舉例說明
- 3、演算法分析
- - 1）前提
  - 2）條件
  - 3）回傳結果
- 4、畫解列舉
- - 1）劃分
  - 2）游標
  - 3）遍歷
  - 4）詳解
- 5、舉一反三
- - 1）大于 x x x 的最小數的下標
  - 2）大于等于 x x x 的最小數的下標
  - 3）小于 x x x 的最大數的下標
  - 4）小于等于 x x x 的最大數的下標
- 6、時間復雜度
二、二分列舉
- 1、二分列舉定義
- 2、舉例說明
- 3、演算法分析
- - 1）目標
  - 2）游標
  - 3）二分
  - 4）時間復雜度
- 4、原始碼詳解
- - 1）條件判定
  - 2）二分列舉模板
- 5、細節決議
- - 1）迭代的程序
  - 2）結束條件
  - 3）游標初始值
  - 4）中點位置
  - 5）死回圈
三、二分列舉的應用
- 1、陣列精確查找
- - 1）題目描述
  - 2）演算法分析
  - 3）原始碼示例
- 2、線性列舉 + 陣列精確查找
- - 1）題目描述
  - 2）演算法分析
  - 3）原始碼示例
- 3、陣列的模糊查找
- - 1）大于等于 x x x 的最小值
  - 2）大于 x x x 的最小值
  - 3）小于等于 x x x 的最大值
  - 4）小于 x x x 的最大值
- 4、單調函數的查找
- - 1）題目描述
  - 2）演算法分析
  - 3）原始碼示例
四、二分列舉的通解
粉絲專屬福利

一、線性列舉

1、線性列舉定義

??線性列舉指的就是遍歷某個一維陣列（順序表）的所有元素，找到滿足條件的那個元素并且回傳，回傳值可以是下標，也可以是元素本身，
??由于是遍歷的，窮舉了所有情況，所以一定是可以找到解的，一些資料上也稱之為暴力演算法（Brute Force），接下來，我們通過一個例子來理解線性列舉，

2、舉例說明

??【例題1】給定一個單調不降的有序陣列 a r r arr arr 和一個值 x x x，要求找到大于 x x x 的最小數的下標，

3、演算法分析

?我們從這個問題中提取幾個關鍵字并分類如下：
??1）前提：單調不降、有序；
??2）條件：大于 x x x、最小數；
??3）回傳結果：下標；

1）前提

??前提就是問題給定時的初始陣列需要滿足的先天性條件，保證資料是能夠符合這個前提的，這里的前提是陣列一定是有序的，且是單調不降的，即 陣列下標大的數 不會比 陣列下標小的數 更小，

2）條件

??這個問題中的條件有兩個：
??1）大于 x x x ；
??2）值最小；
??我們如果仔細分析一下這個問題，就可以發現，正因為這里的陣列是單調不降的，所以，一旦滿足 某個數大于 x x x，之后的所有數必然都滿足 大于 x x x 這個條件，所以我們必然可以把陣列分成兩部分，一部分是 大于 x x x 的，另一部分是 不大于 x x x 的，

3）回傳結果

??這里的回傳結果要求是下標，而我們遍歷操作也是通過遍歷陣列的下標進行的，所以找到滿足條件的，回傳下標即可，

4、畫解列舉

??接下來，我們通過一組實際的資料來解釋這個問題，
a r r = [ 1 , 3 , 4 , 6 , 6 , 6 , 7 , 8 , 9 ] arr = [1, 3, 4, 6, 6, 6, 7, 8, 9] arr=[1,3,4,6,6,6,7,8,9]

1）劃分

??對于這個陣列，當 x = 6 x = 6 x=6 時，我們將陣列分成兩部分，大于 6 的部分用綠色表示，不大于 6 的部分用紅色表示，
??這么表示的目的，主要是為了方便記憶，聯想一下 紅綠燈，綠色代表可以通行，即 “大于6” 這個條件滿足；紅色代表禁止通行，即條件不滿足，

2）游標

??設定一個游標，初始時指向陣列的第 0 個元素（C語言中陣列下標從 0 開始計數），
??游標，顧名思義，就是游動的下標，你也可以叫指標，我之所以沒有稱之為指標，是不想它和C語言中的指標概念混淆，

3）遍歷

??遍歷就是判斷當前游標指向的元素是否是綠色的，如果是綠色的直接回傳，因為它一定是大于 x x x 且值最小的；如果不是，則增加游標的值，繼續下一次判斷，直到陣列遍歷完畢，如下圖所示：

在這里插入圖片描述
??數字 7 就是我們要找到大于 6 的最小數，它的下標為 6，

4）詳解

int isGreen(int val, int x) {               // (1)
    return val > x;
}
int findFirstBiggerThan(int *arr, int arrSize, int x) {
    int i;
    for(i = 0; i < arrSize; ++i) {          // (2)
        if( isGreen(arr[i], x) ) {          // (3)
            return i;
        }
    }
    return arrSize;                         // (4)
}

( 1 ) (1) (1) int isGreen(int val, int x)這個函式代表條件是否滿足，滿足回傳 1，否則回傳 0；這里的條件便是 v a l > x val > x val>x，
( 2 ) (2) (2) 下標從小到大，從 0 開始遍歷陣列 a r r arr arr；
( 3 ) (3) (3) 一旦遇到大于 x x x 的數，則回傳它的下標，因為是下標從小往大遍歷的，所以第一個找到滿足條件的數一定是值最小的；
( 4 ) (4) (4) 如果找不到，說明所有的數都是小于等于 x x x 的，直接回傳陣列長度；

5、舉一反三

??接下來，我們來看看線性列舉的其它幾種問法，

??【例題2】給定一個單調不降的有序陣列如下： [ 1 , 3 , 4 , 6 , 6 , 6 , 7 , 8 , 9 ] [1, 3, 4, 6, 6, 6, 7, 8, 9] [1,3,4,6,6,6,7,8,9]，要求找到以下元素：
???? ( 1 ) (1) (1) > 6 \gt 6 >6 的最小數的下標位置；
???? ( 2 ) (2) (2) ≥ 6 \ge 6 ≥6 的最小數的下標位置；
???? ( 3 ) (3) (3) < 6 \lt 6 <6 的最大數的下標位置；
???? ( 4 ) (4) (4) ≤ 6 \le 6 ≤6 的最大數的下標位置；

?? 對于這四個問題，我們可以發現它們的答案如下所示：

0	1	2	3	4	5	6	7	8
1	3	4	6	6	6	7	8	9
		( 3 ) (3) (3)	( 2 ) (2) (2)		( 4 ) (4) (4)	( 1 ) (1) (1)

1）大于 x x x 的最小數的下標

??將陣列按照條件進行劃分，然后利用上文提到的findFirstBiggerThan函式求解即可，

2）大于等于 x x x 的最小數的下標

??我們把問題做個變形，將問題變成找 大于等于 x x x 的最小數的下標（比之前的問題多了一個等于），按照條件劃分的結果應該是包含 6 本身的，所以如下圖所示：

??遍歷陣列的部分不變，只不過條件變成了 大于等于，C語言實作如下：

int isGreen(int val, int x) {
    return val >= x;              // (1)
}
int findFirstBiggerEqualThan(int *arr, int arrSize, int x) {
    int i;
    for(i = 0; i < arrSize; ++i) {
        if( isGreen(arr[i], x) ) {
            return i;
        }
    }
    return arrSize;
}

( 1 ) (1) (1) 將原先的>號改成>=即可；

3）小于 x x x 的最大數的下標

??上面兩個問題能理解的話，我們再來看一個問題，如何找到 小于 x x x 的最大數的下標 ，要求下標最大，那么我們在列舉的程序中，如果發現一個大于等于 x x x 的數，那么后續都不用列舉了，并且需要回傳這個數的前一個位置，條件劃分如下圖所示：

??我們要做的是回傳紅色中的最大下標，C語言實作如下：

int isGreen(int val, int x) {
    return val >= x;                  // (1)
} 

int findLastSmallThan(int *arr, int arrSize, int x) {
    int i;
    for(i = 0; i < arrSize; ++i) {
        if( isGreen(arr[i], x) ) {
            return i - 1;              
        }
    }
    return arrSize - 1;
}

( 1 ) (1) (1) 大于等于 x x x 時，isGreen成立；
( 2 ) (2) (2) 由于我們要做的是回傳紅色中的最大下標，所以一旦遇到大于等于 x x x 的數（即綠色的情況），則回傳它的前一個下標；
( 3 ) (3) (3) 如果找不到，則回傳 arrSize - 1，即所有數都是紅色的，則最大下標就是陣列的最后一個元素的下標；

4）小于等于 x x x 的最大數的下標

??我們把問題繼續做變形，將問題變成找 小于等于 x x x 的最大數的下標（比之前的問題多了一個等于），劃分如下圖所示：

??遍歷陣列的部分不變，只不過條件變成了大于，我們要做的是回傳紅色中的最大下標，C語言實作如下：

int isGreen(int val, int x) {
    return val > x;             // (1)
} 

int findLastSmallEqualThan(int *arr, int arrSize, int x) {
    int i;
    for(i = 0; i < arrSize; ++i) {
        if( isGreen(arr[i], x) ) {
            return i - 1;              
        }
    }
    return arrSize - 1;
}

( 1 ) (1) (1) 將原先的>=號改成>即可；

6、時間復雜度

??以上的內容就是線性列舉的幾種常見情況，也就是無腦遍歷所有情況，并且在滿足條件的第一時間退出回圈，當陣列長度為 n n n 時，演算法的時間復雜度為 O ( n ) O(n) O(n)，比較低效，有沒有更加高效的演算法呢？
??接下來出場的，就是本文的主角 —— 二分列舉，

二、二分列舉

1、二分列舉定義

??二分列舉，也叫二分查找，指的就是給定一個區間，每次選擇區間的中點，并且判斷區間中點是否滿足某個條件，從而選擇左區間繼續求解還是右區間繼續求解，直到區間長度不能再切分為止，
??由于每次都是把區間折半，又叫折半查找，時間復雜度為 O ( l o g 2 n ) O(log_2n) O(log2?n)，和線性列舉的求解結果一直，但是高效許多，回傳值可以是下標，也可以是元素本身，

2、舉例說明

??【例題3】只有兩種顏色的陣列 a r r arr arr ，左邊部分為紅色用 0 表示，右邊部分為綠色用 1 表示，要求找到下標最小的綠色元素的下標，

如圖所示，下標最小的綠色元素的下標為 3，所以應該回傳 3，

3、演算法分析

1）目標

??對于這個問題，當我們拿到這個陣列的時候，第一個綠色位置在哪里，我們是不知道的，所以，現在的目標就是要通過二分列舉找到紅色區域和綠色區域的邊界，

2）游標

??利用線性列舉的思路，我們引入游標的概念，只不過需要兩個游標，左邊一個紅色游標，右邊一個綠色游標，并且游標初始位置都在陣列以外，對于一個 n n n 個元素的陣列，紅色游標初始位置在 ? 1 -1 ?1，綠色游標初始位置在 n n n，

3）二分

??我們將兩個游標相加，并且除 2，從而得到游標的中點，并且判斷中點所在位置的顏色，發現是綠色的，這說明從 中點游標 到 綠色游標 的元素都是綠色的，如下圖所示：

??于是，我們可以把 綠色游標 替換成 中點游標，如下圖所示：

??這樣就完成了一次二分，區間相比之前，縮小了一半，注意，我們要求的解，一定永遠在 紅色游標 和 綠色游標 之間，
??然后，我們繼續將兩個游標相加，并且除 2，從而得到游標的中點，并且判斷中點所在位置的顏色，發現是紅色的，這說明從 紅色游標 到 中點游標 的元素都是紅色的，如下圖所示：

??于是，我們可以把 紅色游標 替換成 中點游標，如下圖所示：

??同樣上述演算法，再經過兩次二分以后，我們得到了如下結果：

??這個時候，這個時候 紅色游標 和 綠色游標 的位置一定相差 1，并且 綠色游標 的位置就是我們這個問題要求的解，

4）時間復雜度

??由于每次操作都是將區間減小一半，所以時間復雜度為 O ( l o g 2 n ) O(log_2n) O(log2?n)，

4、原始碼詳解

??那么接下來，我們來看下，如何用 C語言來實作這個問題，

1）條件判定

??判斷一個元素是綠色還是紅色，我們可以單獨用一個函式來實作，根據題意，當值為 1 時代表綠色，值為 0 時代表紅色，C語言實作如下：

int isGreen(int val) {
    return val == 1;
}

2）二分列舉模板

??接下來的二分列舉模板可以解決大部分二分列舉的問題，請妥善保管，

int binarySearch(int *arr, int arrSize, int x) {
    int l = -1, r = arrSize;         // (1)
    int mid;
    while(r - l > 1) {               // (2)
        mid = l + (r - l) / 2;       // (3)
        if( isGreen(arr[mid], x) )   // (4)
            r = mid;                 // (5)
        else
            l = mid;                 // (6)
    }
    return r;                        // (7)
}

( 1 ) (1) (1) l l l 代表 紅色游標， r r r 代表 綠色游標；
( 2 ) (2) (2) 當區間長度大于 2 的時候，二分縮小區間，這一步被稱為區間收斂；
( 3 ) (3) (3) m i d mid mid 為計算出來的區間 [ l , r ] [l, r] [l,r] 的中點；
( 4 ) (4) (4) 判斷區間中點對應的元素是綠色還是紅色；
( 5 ) (5) (5) 如果 中點元素 是綠色，則從中點到 r r r 的值都為綠色，用中點替換 綠色游標；
( 6 ) (6) (6) 如果 中點元素 是紅色，則從 l l l 到中點的值都為紅色，用中點替換 紅色游標；
( 7 ) (7) (7) 這個地方是模板需要變通的地方，如果需要回傳紅色邊界，那么應該回傳 l l l；反之，如果需要回傳綠色邊界，則應該回傳 r r r，這個問題中，是后者，

5、細節決議

1）迭代的程序

??整個二分的程序是一個不斷迭代區間的程序，并且 紅色游標 指向的元素始終是紅色的；綠色游標 指向的元素始終是綠色的，迭代的程序就是不斷向 紅綠邊界 逼近的程序，

2）結束條件

??迭代結束時，紅色游標 和 綠色游標 剛好指向 紅綠邊界，且區間長度為 2，

3）游標初始值

??為什么 紅色游標 初始值為 ? 1 -1 ?1，綠色游標 初始值為 n n n ?
??能否將 紅色游標 初始化為 0 0 0，綠色游標 初始化為 n ? 1 n-1 n?1 ? 答案是否定的，試想一下，如果資料元素都是綠色，紅色游標 初始化為 0 就違背了 " 紅色游標 指向的元素始終是紅色的 " 這個條件；反之，如果元素都是紅色的，也有類似問題，

4）中點位置

??由于中點的位置是需要去訪問陣列來獲取值的，所以必須滿足始終在 [ 0 , n ) [0, n) [0,n) 區間范圍內，
??中點位置計算公式為： m i d = ? l + r 2 ? mid = \lfloor \frac {l +r} 2 \rfloor mid=?2l+r??，
?? l l l 的最小值為 ? 1 -1 ?1， r r r 的最小值為 l + 2 l+2 l+2，所以 m i d mid mid 的最小值就是 ? l + r 2 ? = ? ? 1 + ( ? 1 + 2 ) 2 ? = 0 \lfloor \frac {l +r} 2 \rfloor = \lfloor \frac {-1 + (-1 + 2)} 2 \rfloor = 0 ?2l+r??=?2?1+(?1+2)??=0；
?? r r r 的最大值為 n n n， l l l 的最大值為 r ? 2 r-2 r?2，所以 m i d mid mid 的最大值就是 ? l + r 2 ? = ? n + ( n ? 2 ) 2 ? = n ? 1 \lfloor \frac {l + r} 2 \rfloor = \lfloor \frac {n + (n - 2)} 2 \rfloor = n-1 ?2l+r??=?2n+(n?2)??=n?1；
??綜上所述，中點的下標位置始終在 [ 0 , n ) [0, n) [0,n) 區間范圍內，

5）死回圈

??上面的程式模板是否會進入死回圈？
??我們可以這么來看，當區間為 2 時，回圈結束，當區間為 3 時，它一定可以變成區間為 2 的情況，當區間為4時，一定可以變成區間為 2 或者 3 的情況，也就是任何一種情況下，區間一定會減小，并且當等于 2 時，回圈結束，所以不會造成死回圈，

三、二分列舉的應用

??接下來，提供一個通用模板，利用這個模板，只需要修改isGreen函式，就能實作絕大部分的二分列舉問題，


/************** 二分查找 陣列 模板 **************/
/*

  1）傳參的陣列滿足：紅紅紅紅紅紅紅紅綠綠綠綠綠綠綠； 
  2）回傳值：綠色區段的左邊界； 
*/

int isGreen(int val, int x);

int binarySearch(int *arr, int arrSize, int x) {
    int l = -1, r = arrSize;
    int mid;
    while(l + 1 < r) {
        mid = l + (r - l) / 2;
        if( isGreen(arr[mid], x) )
            r = mid;
        else
            l = mid;
    }
    return r;
}
/************** 二分查找 陣列 模板 **************/

??其中，條件函式int isGreen(int val, int x)函式的實作需要根據具體問題具體分析，

1、陣列精確查找

1）題目描述

??【例題4】給定一個 n n n 個元素的升序整型陣列 n u m s nums nums 和一個目標值 x x x，寫一個函式search搜索 n u m s nums nums 中的 t a r g e t target target，如果目標值存在回傳下標，否則回傳 ? 1 -1 ?1，
??原題鏈接：WhereIsHeroFrom/118445716

2）演算法分析

??對于查找 t a r g e t target target 是否存在，我們把陣列中 "大于等于 t a r g e t target target" 的劃分為綠色，其它為紅色，利用模板得到回傳值，回傳值回傳的是 r r r，也就是圖中的綠色箭頭指向位置，需要分三種情況討論：
??1） r = n r = n r=n，所有數都小于 t a r g e t target target，回傳-1；
??2） n u m s [ r ] ≠ t a r g e t nums[r] \neq target nums[r]?=target，代表這個值不存在，回傳-1；
??3） n u m s [ r ] = t a r g e t nums[r] = target nums[r]=target，直接回傳 r r r；
??時間復雜度為 O ( l o g 2 n ) O(log_2n) O(log2?n)，

3）原始碼示例

int isGreen(int val, int x) {
    return val >= x;                   // (1)
}

int search(int* nums, int n, int x){
    int r = binarySearch(nums, n, x);  // (2)
    if(r == n || nums[r] != x)         // (3)
        return -1;
    return r;                          // (4)
}

( 1 ) (1) (1) 劃分綠色邊界；
( 2 ) (2) (2) 呼叫模板，回傳綠色邊界；
( 3 ) (3) (3) 沒有找到解情況；
( 4 ) (4) (4) 找到解的情況；

2、線性列舉 + 陣列精確查找

1）題目描述

??【例題5】輸入一個遞增排序的陣列和一個數字 s s s，在陣列中查找兩個數，使得它們的和正好是 s s s，如果有多對數字的和等于s，則輸出任意一對即可，
??原題鏈接：WhereIsHeroFrom/118507985

2）演算法分析

??我們已經知道在一個陣列中尋找一個數的演算法，那么，我們只需要列舉一個確定的數 x x x，然后再在陣列的剩余部分去查找 s ? x s-x s?x 是否存在，就可以確定兩個數的實際位置了，時間復雜度 O ( n l o g 2 n ) O(nlog_2n) O(nlog2?n)，
??即先做一次線性列舉，再做一次二分列舉，

3）原始碼示例


int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int i, pos, base;
    int *ret = (int *)malloc( sizeof(int) * 2 );  // (1)
    *returnSize = 0;                              // (2)
    for(i = 0; i < numsSize; ++i) {               
        base = i+1;                               // (3)
        pos = search(nums+base , numsSize-base, target - nums[i]); // (4)    
        if(pos != -1) {                           // (5)
            ret[0] = nums[i];
            ret[1] = nums[pos+base];
            *returnSize = 2;
            return ret;
        }
    }
    return ret;
}

( 1 ) (1) (1) 利用malloc申請一塊記憶體空間，用于回傳值；
( 2 ) (2) (2) 將回傳資料的長度設為 0，因為有可能無解；
( 3 ) (3) (3) 升序陣列中的兩個數的和為target，所以我們可以列舉nums[i]，并且在剩下的陣列中列舉，剩下陣列的偏移量為base = i + 1；
( 4 ) (4) (4) 呼叫【例題4】中的精確查找，查找是否存在解；
( 5 ) (5) (5) 回傳值不等于 ? 1 -1 ?1 ，則代表nums[i]和nums[pos+i+1]的和為target，回傳這兩個值組成的陣列即可；

3、陣列的模糊查找

1）大于等于 x x x 的最小值

??【例題6】給定一個排序陣列和一個目標值 t a r g e t target target，在陣列中找到目標值，并回傳其索引，如果目標值不存在于陣列中，回傳它將會被按順序插入的位置，
??原題鏈接：WhereIsHeroFrom/118452682

??首先，我們需要考慮一下，插入的這個位置，需要滿足什么條件？
??如果我們對陣列進行劃分，大于等于目標值的作為綠色元素，其余作為紅色元素，如果有目標值，那么綠色元素的左邊界就是我們要找的索引；如果沒有目標值，那么紅色的右邊界一定比我們要插入的數小，綠色元素的左邊界一定比我們要插入的元素大，所以綠色元素的左邊界也是我們要找的索引，

??綜上所述，我們就是要找到綠色元素的左邊界，直接套用上面的二分列舉的模板即可，其中isGreen函式實作如下：

int isGreen(int val, int x) {
    return val >= x;
}

2）大于 x x x 的最小值

??【例題7】給你一個排序后的字串列letters，串列中只包含小寫英文字母，另給出一個目標字母target，請你尋找在這一有序串列里比目標字母大的最小字母，
??原題鏈接：WhereIsHeroFrom/120754725

??如果我們對陣列進行劃分，大于目標值的作為綠色元素，其余作為紅色元素，那么顯而易見，我們只要找到這個綠色元素的左邊界，就找到了大于目標值的最小值，
??綜上所述，我們就是要找到綠色元素的左邊界，直接套用上面的二分列舉的模板即可，其中isGreen函式實作如下：

int isGreen(int val, int x) {
    return val > x;
}

3）小于等于 x x x 的最大值

??【例題8】給你一個排序后的遞增陣列和一個目標值 t a r g e t target target，要求找到小于等于 t a r g e t target target 的最大值的下標，

??如果我們對陣列進行劃分，大于目標值的作為綠色元素，其余作為紅色元素，那么顯而易見，我們只要找到這個紅色元素的右邊界，就找到了小于等于目標值的最大值，

??綜上所述，直接套用上面的二分列舉的模板，并且對回傳值減一即可，其中isGreen函式實作如下：

int isGreen(int val, int x) {
    return val > x;
}

4）小于 x x x 的最大值

??【例題9】給你一個排序后的遞增陣列和一個目標值 t a r g e t target target，要求找到小于 t a r g e t target target 的最大值的下標，

??如果我們對陣列進行劃分，大于等于目標值的作為綠色元素，其余作為紅色元素，那么顯而易見，我們只要找到這個紅色元素的右邊界，就找到了小于目標值的最大值，

??綜上所述，直接套用上面的二分列舉的模板，并且對回傳值減一即可，其中isGreen函式實作如下：

int isGreen(int val, int x) {
    return val >= x;
}

??有關陣列的模糊查找問題，列出表格如下：

模糊查找	綠色部分條件	回傳值
大于等于 x x x 的最小值	≥ x \ge x ≥x	r r r
大于 x x x 的最小值	> x \gt x >x	r r r
小于等于 x x x 的最大值	> x \gt x >x	l l l
小于 x x x 的最大值	≥ x \ge x ≥x	l l l

4、單調函式的查找

??二分查找除了能夠在陣列中找到可行解，也能夠在單調函式中找到可行解，同樣是將函式根據定義域劃分成兩部分，左邊為紅色，右邊為綠色，然后找到邊界紅綠邊界，根據實際情況選擇紅色邊界或者綠色邊界，
??相應的，二分列舉的模板需要做適當的修改，傳入的引數由原先的陣列，變成了一個區間，C語言實作如下：

/**************二分查找模板 回傳綠色邊界**************/
int isGreen(int val, int x);

int binarySearch(int l, int r, int x) {
    int mid;
    while(l + 1 < r) {
        mid = l + (r - l) / 2;
        if( isGreen(mid, x) )
            r = mid;
        else
            l = mid;
    }
    return r;
}
/**************二分查找模板 回傳綠色邊界**************/

1）題目描述

??【例題10】給你一個非負整數 x x x ，計算并回傳 x x x 的算術平方根，由于回傳型別是整數，結果只保留整數部分，小數部分將被舍去，
??原題鏈接：WhereIsHeroFrom/119976200

2）演算法分析

??考慮 f ( x ) = x 2 f(x) = x^2 f(x)=x2 這個函式，當 x x x 遞增時，函式的值越來越大，是一個單調遞增函式，我們現在要做的就是，找到 f ( k ) f(k) f(k) 使得 f ( k ) f(k) f(k) 小于等于 x x x，且盡量大，并且回傳 k k k 的值，
??當 x = 0 x=0 x=0, x = 1 x=1 x=1 時，我們可以直接回傳 x x x；當 x > 1 x > 1 x>1時，我們構造紅綠邊界，所有 f ( k ) ≤ x f(k) \le x f(k)≤x 的情況為紅色，反之， f ( k ) > x f(k) \gt x f(k)>x 的情況為綠色，然后通過二分找到紅色邊界就是答案了，

3）原始碼示例

int isGreen(int val, int x) {
    return (long long)val * val > x;  // (1)    
}

int mySqrt(int x){
    int r;
    if(x == 0 || x == 1) {
        return x;
    }
    r = binarySearch(0, x, x);        // (2)
    return r - 1;                     // (3)
}

( 1 ) (1) (1) 構造綠色部分為 k 2 > x k^2 \gt x k2>x，那么紅色部分就是 k 2 ≤ x k^2 \le x k2≤x；
( 2 ) (2) (2) 找到綠色邊界；
( 3 ) (3) (3) 回傳紅色邊界；

四、二分列舉的通解

??任何可以用二分列舉來求解的問題，都可以抽象出一個單調函式，并且將單調函式劃分成紅色和綠色兩部分，通過二分列舉求出紅綠邊界，然后再根據條件來決定是回傳紅色的右邊界，還是綠色的左邊界，簡化為以下四步：

??1）抽象出單調函式；
??2）確定isGreen函式；
??3）二分列舉求出紅綠邊界；
??4）確定回傳紅色邊界還是綠色邊界；

??關于 「二分查找」 的內容到這里就結束了，
??如果還有不懂的問題，可以通過 「電腦版主頁」找到作者的「聯系方式」 ，線上溝通交流，

??有關🌳《畫解資料結構》🌳 的原始碼均開源，鏈接如下：《畫解資料結構》

??相信看我文章的大多數都是「大學生」，能上大學的都是「精英」，那么我們自然要「精益求精」，如果你還是「大一」，那么太好了，你擁有大把時間，當然你可以選擇「刷劇」，然而，「學好演算法」，三年后的你自然「不能同日而語」，
??那么這里，我整理了「幾十個基礎演算法」 的分類，點擊開啟：

🌌《演算法入門指引》🌌
??如果鏈接被屏蔽，或者有權限問題，可以私聊作者解決，

在這里插入圖片描述

🔥讓天下沒有難學的演算法🔥
C語言免費動漫教程，和我一起打卡！ 🌞《光天化日學C語言》🌞
入門級C語言真題匯總 🧡《C語言入門100例》🧡
幾張動圖學會一種資料結構 🌳《畫解資料結構》🌳
組團學習，抱團生長 🌌《演算法入門指引》🌌
競賽選手金典圖文教程 💜《夜深人靜寫演算法》💜

粉絲專屬福利

語言入門：《光天化日學C語言》(示例代碼)
語言訓練：《C語言入門100例》試用版
資料結構：《畫解資料結構》原始碼
演算法入門：《演算法入門》指引
演算法進階：《夜深人靜寫演算法》演算法模板

👇🏻 關注公眾號 獲取更多資料👇🏻

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/325590.html

標籤：其他

上一篇：單鏈表基礎知識詳解——基本概念結構及函式實作(增刪查改)

下一篇：自然數的串列=>回傳布林值

視頻解說：簡易版二分查找

前言

文章目錄

一、線性列舉

1、線性列舉定義

2、舉例說明

3、演算法分析

1）前提

2）條件

3）回傳結果

4、畫解列舉

1）劃分

2）游標

3）遍歷

4）詳解

5、舉一反三

1）大于 x x x 的最小數的下標

2）大于等于 x x x 的最小數的下標

3）小于 x x x 的最大數的下標

4）小于等于 x x x 的最大數的下標

6、時間復雜度

二、二分列舉

1、二分列舉定義

2、舉例說明

3、演算法分析

1）目標

2）游標

3）二分

4）時間復雜度

4、原始碼詳解

1）條件判定

2）二分列舉模板

5、細節決議

1）迭代的程序

2）結束條件

3）游標初始值

4）中點位置

5）死回圈

三、二分列舉的應用

1、陣列精確查找

1）題目描述

2）演算法分析

3）原始碼示例

2、線性列舉 + 陣列精確查找

1）題目描述

2）演算法分析

3）原始碼示例

3、陣列的模糊查找

1）大于等于 x x x 的最小值

2）大于 x x x 的最小值

3）小于等于 x x x 的最大值

4）小于 x x x 的最大值

4、單調函式的查找

1）題目描述

2）演算法分析

3）原始碼示例

四、二分列舉的通解

粉絲專屬福利