在計(jì)算機(jī)領(lǐng)域，二分查找又叫折半查找，有的地方根據(jù)其時(shí)間復(fù)雜度把它叫做對(duì)數(shù)查找，它能在對(duì)數(shù)時(shí)間內(nèi)找到指定的元素，本篇文章介紹二分查找的基礎(chǔ)和原理。

原理

二分查找算法是一種在有序數(shù)組中查找特定元素的查找算法，查找過(guò)程從數(shù)組的中間元素開(kāi)始。

• 如果中間元素剛好是要查找的元素，則查找結(jié)束。
• 如果比中間元素的值小，則在數(shù)組起始到小于中間元素的那一半之間查找，而且也是從這一半兒的中間位置開(kāi)始比較。
• 如果比中間元素的值大，則在數(shù)組大于中間元素到末尾元素的那一半兒之間查找，同樣還是從這一半兒的中間位置開(kāi)始比較。

這里有一個(gè)有序數(shù)組，元素的索引從 0 到 6，我們以它為例來(lái)說(shuō)明二分查找的過(guò)程：

• 查找值為 15 的元素；

15 剛好位于數(shù)組中間的位置，所以比較一次就找到了；

• 查找值為 8 的元素；

數(shù)組中間位置的元素是 15，目標(biāo)值 8 小于 15，所以查找范圍縮小到 15 左邊的一半,也即 [ 3 , 9 ] ,這一半中間位置的元素是 8，剛好是要查找的值；

• 查找值為 34 的元素；

數(shù)組中間位置的元素是 15，目標(biāo)值 34 大于 15，所以查找范圍縮小到 15 右邊的一半，也即 [ 19 , 34] ,它們的中間元素是 20，目標(biāo)值 34 比 20 大，所以查找范圍繼續(xù)減半為 [ 34, 34 ] , 它們的中間元素是 34, 剛好是要查找的值。

基本框架

根據(jù)上述二分查找的流程，可以總結(jié)出二分查找的基本框架, 下面是偽代碼：

int binary_search(vector<int> &vec, int target)
{
    int left = 0;      //查找范圍的左邊索引
    int right  = 0;    //查找范圍的右邊索引
    while(...)  //查找結(jié)束條件
    {
        //數(shù)組中間元素的索引
        int mid = left + (right - left) / 2;
        //和目標(biāo)值相等
        if(target == vec[mid]) 
        {
            //處理邏輯
            ...
        }
        //目標(biāo)值小于中間元素
        else if(target < vec[mid]) 
        {
            //處理邏輯
            left = ...
        }
        //目標(biāo)值大于中間元素
        else 
        {
            //處理邏輯
            right = ...
        }
    }
    //返回目標(biāo)值在索引中的位置，如果找不到，返回 -1
    return ...
}

偽代碼中的 ... 的地方是容易出現(xiàn)細(xì)節(jié)問(wèn)題的地方, 我們自己編寫(xiě)或者看別人代碼的時(shí)候，注意下這些地方。

需要注意一點(diǎn)，計(jì)算查找范圍的中間位置的索引的方法 mid = (left + right) / 2, 當(dāng)數(shù)組非常大的時(shí)候, left + right 可能會(huì)超過(guò)整形最大值，所以需要修改成 mid = left + (right - left) / 2 或者 mid = left + (right - left) >> 1, 以避免溢出風(fēng)險(xiǎn)。

實(shí)現(xiàn)

二分查找的實(shí)現(xiàn)方式有多種，這里只選取前面基本框架中的方式來(lái)介紹，常見(jiàn)的二分查找場(chǎng)景有：查找一個(gè)指定的數(shù)、查找數(shù)組中第一個(gè)和目標(biāo)值相等的元素，查找數(shù)組中最后一個(gè)和目標(biāo)值相等的元素。

下面的算法實(shí)現(xiàn)代碼是用 C++ 語(yǔ)言實(shí)現(xiàn)的，vector vec 表示一個(gè)整形的數(shù)組, 數(shù)組名是 vec ，類(lèi)似于 Java 中的 int[] nums, 如果是 C語(yǔ)言的話(huà)，可以用 int *nums 和 int len 來(lái)表示也是一樣的，大家可以自行用熟悉的編程語(yǔ)言實(shí)現(xiàn)。

1. 查找和目標(biāo)值相等的元素

這是最基礎(chǔ)的二分查找，只要找到了和目標(biāo)值相等的元素，返回其索引，否則返回 -1，表示沒(méi)找到和目標(biāo)值相等元素的索引：

int binary_search(vector<int> &vec, int target)
{
    int ilen = (int)vec.size();
    if(ilen <= 0) return -1;
    int left = 0;
    int right = ilen - 1;
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        //找到了,直接返回
        if (target == vec[mid]) return mid;
        if(target < vec[mid]) right = mid -1;
        else left = mid + 1;        
    }
    return -1;
}

需要注意幾點(diǎn):

• 為什么 while 的循環(huán)條件是 <=；

因?yàn)?right = ilen - 1 , 也就最后一個(gè)元素的索引, 當(dāng) left 等于 right 的時(shí)候, 表示 到達(dá)查找范圍右邊的邊界。

此時(shí) mid = left = right, 當(dāng) mid 索引處的元素和目標(biāo)值相等時(shí), 返回索引 mid。

如果不相等, 要么 left = mid + 1 要么 right = mid -1 ，不管執(zhí)行哪個(gè)邏輯，結(jié)果都是 left > right, 接著退出 while 循環(huán)。

• 為什么 left = mid + 1 或者 right = mid - 1；

根據(jù)前面的介紹可知，二分查找的范圍是 [left, right], 當(dāng)我們發(fā)現(xiàn)查找的目標(biāo)值不等于 mid 索引元素的值時(shí), 下一次查找的范圍是 [left, mid - 1] 或者 [mid + 1, right], 因?yàn)?mid 處的元素已經(jīng)比較過(guò)了，需要從查找范圍中排除。

2. 第一個(gè)和目標(biāo)值相等的元素

上面的二分查找有一個(gè)局限性，比如一個(gè)有序數(shù)組 {-1,-1,-1,-1，2,3}, target 的值為 -1, 此時(shí)算法返回的索引是 2, 結(jié)果是沒(méi)錯(cuò)，但如果我想得到第一個(gè)和 target 相等元素的索引，也即 0 或者最后一個(gè)和 target 相等元素的索引, 也即 3 時(shí), 此算法是沒(méi)辦法處理的, 下面就來(lái)說(shuō)明這兩種二分查找算法。

int binary_search_firstequal(vector<int> &vec, int target)
{
    int ilen = (int)vec.size();
    if(ilen <= 0) return -1;
    int left = 0;
    int right = ilen - 1;
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        //找到了目標(biāo),繼續(xù)向左查找目標(biāo)
        if (target == vec[mid]) right = mid - 1;
        else if(target < vec[mid]) right = mid -1;
        else left = mid + 1;        
    }
    if(left < ilen && vec[left] == target) return left;
    return -1;
}

當(dāng)條件 target == vec[mid] 以及 target < vec[mid] 成立時(shí)，都執(zhí)行 right = mid - 1的邏輯, 這里把它們分開(kāi)是為了便于大家理解，熟練以后，兩個(gè)條件合并成一個(gè)。

• 為什么 target == vec[mid] 時(shí) right = mid - 1；

當(dāng) mid 索引處的值和目標(biāo)值相等時(shí), 我們需要在 mid 的左邊繼續(xù)查找 , 看是否存在和目標(biāo)值相同的元素, 所以查找范圍變成了 [ left, mid - 1] , 故需要執(zhí)行 right = mid - 1的邏輯。

• 為什么最后返回時(shí)要加上 left < ilen && vec[left] == target 的條件；

while 循環(huán)退出條件是 left = right + 1, 當(dāng) target 的值比數(shù)組中元素的值都大的時(shí)候, left 索引的值會(huì)超過(guò)數(shù)組的最大索引, 所以需要進(jìn)行索引邊界校驗(yàn)，也即 left < ilen。

當(dāng) target 的值處于數(shù)組最大元素和最小元素之間且數(shù)組中不存在和target 值相等的元素時(shí), 此時(shí)無(wú)法找到一個(gè)索引，使得元素的值和 target 相等, 所以，還需要進(jìn)行 vec[left] == target 的邏輯判斷。

• 為什么返回 left 而不是 right；

也可以返回 right, 把最后的判斷改成 if ( right + 1 < ilen && vec[right + 1] == target) return right+1; 即可。

當(dāng)找到數(shù)組中第一個(gè)和目標(biāo)值相等的元素時(shí), 執(zhí)行了 right = mid - 1, 然后就退出了 while 循環(huán), 而實(shí)際的索引值應(yīng)該是 mid , 也就是 right + 1。

3. 最后一個(gè)和目標(biāo)值相等的元素

和 查找第一個(gè)和目標(biāo)值相等的元素 算法稍有不同, 此二分查找算法找到和目標(biāo)值相等元素之后，查找范圍需要往右移動(dòng),繼續(xù)找下一個(gè)和目標(biāo)值相等的元素。

int binary_search_lastequal(vector<int> &vec, int target)
{
    int ilen = (int)vec.size();
    if(ilen <= 0) return -1;
    int left = 0;
    int right = ilen - 1;
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        //找到了目標(biāo)，繼續(xù)向右查找目標(biāo)
        if (target == vec[mid]) left = mid + 1;
        else if(target < vec[mid]) right = mid -1;
        else left = mid + 1;        
    }
    if(left - 1 < ilen && vec[left - 1] == target) return left - 1;
    return -1;
}

有幾個(gè)細(xì)節(jié)需要注意下：

• 為什么 target == vec[mid] 時(shí) left = mid + 1；

當(dāng) mid 索引處的值和目標(biāo)值相等時(shí), 我們需要在 mid 的右邊繼續(xù)查找 , 看是否存在和目標(biāo)值相同的元素, 所以查找范圍變成了 [ mid + 1, right] , 故需要執(zhí)行 left = mid + 1的邏輯。

• 為什么最后返回時(shí)要加上 left - 1 < ilen && vec[left - 1] == target 的條件；

當(dāng) target 大于或者等于數(shù)組中元素的時(shí)候, 查找范圍左邊的邊界會(huì)右移，即 left = mid + 1, 即使找到了最后一個(gè)和目標(biāo)值相等的元素時(shí)，left 還是會(huì)向右移動(dòng)一個(gè)位置，所以，實(shí)際的位置是 left - 1 而不是 left。

當(dāng) target 的值處于數(shù)組最大元素和最小元素之間且數(shù)組中不存在和target 值相等的元素時(shí), 此時(shí)無(wú)法找到一個(gè)索引，使得元素的值和 target 相等, 所以，還需要進(jìn)行 vec[left-1] == target 的邏輯判斷。

小結(jié)

本文介紹了二分查找算法的原理以及常見(jiàn)的實(shí)現(xiàn)方式，網(wǎng)上還有很多其他的實(shí)現(xiàn)方式，比如：遞歸的方式、左閉右開(kāi)的查找范圍的方式，它們的原理都是一樣的，只是在細(xì)節(jié)上有差別，只要弄清楚了本文介紹的所有細(xì)節(jié)處理的原因，其他版本的二分查找是很容易就能弄明白的。