🎈 作者：Linux猿

🎈 簡介：CSDN博客專家🏆，華為云享專家🏆，Linux、C/C++、面試、刷題、演算法盡管咨詢我，關注我，有問題私聊！

🎈 關注專欄：圖解資料結構和演算法（優質好文持續更新中……）🚀

🎈 歡迎小伙伴們點贊👍、收藏?、留言💬

🍓一、什么是二分查找演算法？

🍓二、二分查找演算法

🚩2.1 普通二分查找

?2.1.1 演算法步驟

?2.1.2 動圖演示

?2.1.3 代碼實作

🚩2.2 二分查找下界

?2.2.1 演算法步驟

?2.2.2 動圖演示

?2.2.3 代碼實作

🚩2.3 二分查找上界

?2.2.1 演算法步驟

?2.2.2 動圖演示

?2.2.3 代碼實作

🍓三、STL 中的二分查找函式

🚩3.0 頭檔案

🚩3.1 普通二分查找

?3.1.1 函式介紹

?3.1.2 代碼示例

🚩3.2 二分查找下界

?3.2.1 函式介紹

?3.2.2 代碼示例

🚩3.3 二分查找上界

?3.3.1 函式介紹

?3.3.2 代碼示例

🍓四、復雜度分析

🚩4.1 時間復雜度

🚩4.2 空間復雜度

🍓五、總結

在資料結構和演算法的學習中，需要查找資料時，經常使用到二分查找演算法，下面就來詳細講解下二分查找的各種用法，

🍓一、什么是二分查找演算法？

二分查找演算法是在有序序列中查找某一特定元素的查找演算法，所謂 “二分”，即：每次查找可以排除一半的元素，所以時間復雜度為 O(log2^n)，因此也被稱為折半查找（指的是對半排除元素），對數查找（對數指的時間復雜度中的對數），

________🐌 我是分割線 🐢________

🍓二、二分查找演算法

🚩2.1 普通二分查找

?2.1.1 演算法步驟

假設存在長度為 n 的升序陣列 A[]，查找元素 target 是否存在，

注意：陣列降序也是可以的，二分查找一般情況下是升序或降序，符合特定規則的升序和降序也是可以的，比如：兩段升序的拼接，這里以升序為例進行講解，

（0）首先，初始化 left = 0, right = n，表示查找的區間為 [ left，right)，最開始時，查找的區間為 [0, n)；

（1）計算 left 和 right 的中間節點，中間節點的下標為 mid = (left + right) /2 ，

（2）然后，判斷 target 與中間節點值 A[ mid ] 的大小；

（3）如果 target = A[ mid ] ，說明在陣列 A 中找到了元素 target，結束查詢；

（4）如果 target < A [ mid ] ，說明，target 并不在陣列 A 的區間 [mid, right) 中，因為陣列 A 是升序陣列，所以 target 應該在區間 [left，mid) 中，所以 left 值不變，讓 right = mid；

（5）否則，target > A[ mid ]，說明，target 在區間 [ mid + 1，right) 中，同樣，是因為陣列 A 是升序陣列，所以 right 的值不變，讓 left = mid + 1；

（6）重復步驟（1）~（5），直到查找到 target 或 left >= right 為止，如果出現 left >= right（這時區間為空，沒有元素了），則表示陣列 A 中沒有找到 target ，

?2.1.2 動圖演示

來看一下動圖演示，假設升序陣列 A[] = {1, 3, 5, 7, 9, 11, 13}，查找 target = 1，如下所示：

在上述動圖中，一共查找了三次，第三次 mid = 0，便查找到了 target = 1，具體查找步驟如下所示：

（1）、最開始查找范圍為 [0, 7)，left = 0, right = 7, 計算 mid = 3；

（2）、縮小查找范圍為 left = 0, right = 3，查找范圍為 [ 0, 3)，重新計算 mid = 1；

（3）、再次縮小查找范圍 left = 0, right = 1，查找范圍為 [0, 1)，重新計算 mid = 0；

（4）、A[ mid = 0 ] = 1 ，查找到 target，

上述就是二分查找陣列 A 中 1 的程序，

?2.1.3 代碼實作

/*
      A[]  : 升序陣列，假設要排序的元素為n個
     left  : 排序陣列的左邊的值，初始為 0
     right : 排序陣列的右邊的值，初始為 n，切記不是n-1
    target : 要查找的值
*/
int binarySearch(int A[], int n, int target){
    int left = 0, right = n;
    while(left < right){ // 查找的區間為 [left, right)
        int mid = (left + right) / 2; // 更好的方法是：mid = left + (right - left) / 2 能防止溢位
        if(A[mid] == target) return mid;
        else if(A[mid] > target) right = mid;
        else left = mid + 1;
    }
    return -1; // 查找不到
}

在計算 mid 的時候，可以使用如下方式：

mid = left + (right - left) / 2

能夠方式 left + right 的溢位，

🚩2.2 二分查找下界

?2.2.1 演算法步驟

假設存在長度為 n 的升序陣列 A[]，陣列中存在重復的元素，要查找元素 target 的最小下標，如下所示：

（0）首先，初始化 left = 0, right = n，表示查找的區間為 [ left，right)，最開始時，查找的區間為 [0, n)；

（1）計算 left 和 right 的中間節點，中間節點的下標為 mid = (left + right) /2 ，

（2）然后，判斷 target 與中間節點值 A[ mid ] 的大小；

（3）如果 A[ mid ] >= target，因為查找的是下界，所以 target 在區間 [ left, mid) 區間還可能存在，所以進一步縮小空間，將查找區間縮小為 [left, mid)，所以 left 值不變，讓 right = mid；

（4）否則，A[ mid ] < target，說明 target 在區間 [ mid + 1，right) 中，因為陣列 A 是升序陣列，所以 right 的值不變，讓 left = mid + 1；

（5）重復步驟（1）~（4），直到跳出 while 回圈；

（6）如果 right 等于 n 或 A [ right ] != target ，則表示未查找到 target，否則 A[ right ] = target，right 為陣列 A 中值為 target 的最小下標；

?2.2.2 動圖演示

來看一下動圖演示，假設升序陣列 A[] = {1, 3, 3, 3, 9, 11, 13}，查找 target = 3，如下所示：

在上述動圖中，一共查找了三次，第三次 mid = 0 結束查找（代碼中是 left == right 跳出 while 回圈）right 指向的值等于 target，具體查找步驟如下所示：

（1）、最開始查找范圍為 [0, 7)，left = 0, right = 7, 計算 mid = 3；

（2）、因為[0, 3) 中可能還存在 target，縮小查找范圍為 left = 0, right = 3，新查找范圍為 [ 0, 3)，重新計算 mid = 1；

（3）、因為[0, 1) 中可能還存在 target，再次縮小查找范圍 left = 0, right = 1，新查找范圍為 [0, 1)，重新計算 mid = 0；

（4）、left 重新計算后，left == right，結束查找，right 指向的值等于 target，

上述就是二分查找陣列 A 中 3 的最小下標的程序，

?2.2.3 代碼實作

/*
      A[] : 升序陣列，假設要排序的元素為 n 個
     left : 查找區間的最左邊的下標，初始為 0
    right : 查找區間的最右邊的下標，初始為 n
    target: 要查找的值
*/
int lowerSearch(int A[], int n, int target){
    int left = 0, right = n;
    while(left < right){
        int mid = left + (right - left)/2;
        if(A[mid] >= target) right = mid;
        else left = mid + 1;
    }
    if(right == n || A[right] != target)
        return -1;
    return right;
}

注意：需要判斷 right 是否是指向 target，因為查找陣列中可能就不存在 target，

🚩2.3 二分查找上界

?2.2.1 演算法步驟

假設存在長度為 n 的升序陣列 A[]，陣列中存在重復的元素，要查找元素 target 的最大下標，如下所示：

（0）首先，初始化 left = 0, right = n，表示查找的區間為 [ left，right)，最開始時，查找的區間為 [0, n)；

（1）計算 left 和 right 的中間節點，中間節點的下標為 mid = (left + right) /2 ，

（2）然后，判斷 target 與中間節點值 A[ mid ] 的大小；

（3）如果 A[mid] > target，所以 target 在區間 [ left，mid) 中，所以縮小空間，將查找區間縮小為 [left, mid)，所以 left 值不變，讓 right = mid；

（4）否則，A[ mid ] <= target，說明 target 在區間 [ mid + 1，right) 中還可能存在，因為陣列 A 是升序陣列，所以 right 的值不變，讓 left = mid + 1；

（5）重復步驟（1）~（4），直到跳出 while 回圈，left --，因為 left 指向的永遠是比 target 大的值的下標；

（6）如果新的 left 等于 n 或 A [ left ] != target ，則表示未查找到 target，否則 A[ left ] = target，right 為陣列 A 中值為 target 的最小下標；

?2.2.2 動圖演示

來看一下動圖演示，假設升序陣列 A[] = {1, 3, 3, 3, 9, 11, 13}，查找 target = 3，如下所示：

在上述動圖中，一共查找了三次，第三次 mid = 4 結束查找（代碼中是 left == right 跳出 while 回圈）left - 1 指向的值等于 target，具體查找步驟如下所示：

（1）、最開始查找范圍為 [0, 7)，left = 0, right = 7, 計算 mid = 3；

（2）、因為[4, 7) 中可能還存在 target，縮小查找范圍為 left = 4, right = 7，新查找范圍為 [ 4, 7)，重新計算 mid = 5；

（3）、因為[4, 5) 中可能還存在 target，再次縮小查找范圍 left = 4, right = 5，新查找范圍為 [4, 5)，重新計算 mid = 4；

（4）、left 重新計算后，left == right，結束查找，left - 1 指向的值等于 target，

上述就是二分查找陣列 A 中 3 的最大下標的程序，

?2.2.3 代碼實作

/*
      A[] : 升序陣列，假設要排序的元素為 n 個
     left : 查找區間的最左邊的下標，初始為 0
    right : 查找區間的最右邊的下標，初始為 n
    target: 要查找的值
*/
int upperSearch(int A[], int n, int target){
    int left = 0, right = n;
    while(left < right){
        int mid = left + (right - left)/2;
        if(A[mid] > target) right = mid;
        else left = mid + 1;
    }
    left--;
    if(left == n || A[left] != target)
        return -1;
    return left;
}

這里需要注意，left 是查找值更大值的下標，所以讓 left --，還需要判斷一下 left 所指向的值是否是 target，因為可能在查找陣列中就不存在 target，

________🐌 我是分割線 🐢________

🍓三、STL 中的二分查找函式

🚩3.0 頭檔案

使用 STL 中的二分查找函式，需要引入如下頭檔案：

#include <algorithm>

🚩3.1 普通二分查找

?3.1.1 函式介紹

函式如下所示：

binary_search(A, A + n, target)

其中：

binary_search : 函式名；

A : 查找的陣列；

n : 陣列 A 的長度；

target : 查找的目標值

?3.1.2 代碼示例

#include <iostream>
#include <algorithm> // 頭檔案
using namespace std;

int main()
{
    int n = 8;
    int A[] = {1, 3, 5, 7, 9, 11, 13, 15};

    cout<<binary_search(A, A + n, 9)<<endl;
    return 0;
}

上述代碼中，查找陣列 A 中是否存在 9，輸出結果為 1，

🚩3.2 二分查找下界

?3.2.1 函式介紹

函式如下所示：

lower_bound(A, A + n, 3)

其中：

lower_bound : 函式名；

A : 查找的陣列；

n : 陣列 A 的長度；

target : 查找的目標值；

注意：函式 lower_bound 回傳的是陣列目標值最小下標的地址，想要計算下標，需要減去陣列 A 的首地址，

?3.2.2 代碼示例

#include <iostream>
#include <algorithm> // 頭檔案
using namespace std;

int main()
{
    int n = 8;
    int A[] = {1, 3, 3, 3, 9, 11, 13, 15};

    cout<<lower_bound(A, A + n, 3) - A<<endl;
    return 0;
}

如上所示，計算下標值需要減去陣列 A 的首地址，輸出為 1，

🚩3.3 二分查找上界

?3.3.1 函式介紹

函式如下所示：

upper_bound(A, A + n, 3)

其中：

lower_bound : 函式名；

A : 查找的陣列；

n : 陣列 A 的長度；

target : 查找的目標值；

注意：函式 upper_bound 回傳的是陣列目標值第一個大于目標值的地址，想要計算下標，需要減去陣列 A 的首地址，

?3.3.2 代碼示例

#include <iostream>
#include <algorithm> // 頭檔案
using namespace std;

int main()
{
    int n = 8;
    int A[] = {1, 3, 3, 3, 9, 11, 13, 15};

    cout<<upper_bound(A, A + n, 3) - A<<endl;
    return 0;
}

注意：上述回傳的是大于目標值的第一個元素的下標，輸出為 4，

________🐌 我是分割線 🐢________

🍓四、復雜度分析

🚩4.1 時間復雜度

每次查找都是排除一半的情況（縮減一半），相當于每次都除以 2，假設長度為 n，查找次數為 x，則 2^x <= n ，x 約等于 log2^n，所以時間復雜度為 O(log2^n)，

🚩4.2 空間復雜度

通常二分查找并不需要額外的輔助空間，所以空間復雜度為 O(1)，

________🐌 我是分割線 🐢________

🍓五、總結

最長使用的還是普通的二分查找演算法，特殊情況會查找上界或下界，當然，可以使用 STL 中的庫函式，

歡迎關注下方👇👇👇公眾號👇👇👇，獲取更多優質內容🤞（比心）！

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

標籤：其他

上一篇：一文搞掂十大經典排序演算法

下一篇：Jörg Schilling逝世：創建CD刻錄工具cdrtools，一生致力于開源

??【資料結構和演算法】動圖演示，超詳細，就怕你不會！二分查找詳解【建議收藏】??

🍓一、什么是二分查找演算法 ？

🍓二、二分查找演算法

🚩2.1 普通二分查找

?2.1.1 演算法步驟

?2.1.2 動圖演示

?2.1.3 代碼實作

🚩2.2 二分查找下界

?2.2.1 演算法步驟

?2.2.2 動圖演示

?2.2.3 代碼實作

🚩2.3 二分查找上界

?2.2.1 演算法步驟

?2.2.2 動圖演示

?2.2.3 代碼實作

🍓三、STL 中的二分查找函式

🚩3.0 頭檔案

🚩3.1 普通二分查找

?3.1.1 函式介紹

?3.1.2 代碼示例

🚩3.2 二分查找下界

?3.2.1 函式介紹

?3.2.2 代碼示例

🚩3.3 二分查找上界

?3.3.1 函式介紹

?3.3.2 代碼示例

🍓四、復雜度分析

🚩4.1 時間復雜度

🚩4.2 空間復雜度

🍓五、總結

🍓一、什么是二分查找演算法？