二分查找（英語(yǔ)：binary search），也稱折半查找（英語(yǔ)：half-interval search）、對(duì)數(shù)搜索（英語(yǔ)：logarithmic search），是用來(lái)在一個(gè)有序數(shù)組中查找某一元素的算法。

二分查找算法僅適用于有序序列，它只能用在升序序列或者降序序列中查找目標(biāo)元素。

一、工作原理

以在一個(gè)升序數(shù)組中查找一個(gè)數(shù)為例。

它每次考察數(shù)組當(dāng)前部分的中間元素，如果中間元素剛好是要找的，就結(jié)束搜索過(guò)程；如果中間元素小于所查找的值，那么左側(cè)的只會(huì)更小，不會(huì)有所查找的元素，只需到右側(cè)查找；如果中間元素大于所查找的值同理，只需到左側(cè)查找。

二、性質(zhì)

（1）時(shí)間復(fù)雜度

二分查找的最優(yōu)時(shí)間復(fù)雜度為O(1) 。

二分查找的平均時(shí)間復(fù)雜度和最壞時(shí)間復(fù)雜度均為 O(logn)。因?yàn)樵诙炙阉鬟^(guò)程中，算法每次都把查詢的區(qū)間減半，所以對(duì)于一個(gè)長(zhǎng)度為n 的數(shù)組，至多會(huì)進(jìn)行 O(logn) 次查找。

（2）空間復(fù)雜度

迭代版本的二分查找的空間復(fù)雜度為O(1) 。

遞歸（無(wú)尾調(diào)用消除）版本的二分查找的空間復(fù)雜度為O(logn) 。

三、二分查找算法原理

（1）若待查序列為空，則返回-1，并退出算法；

（2）若待查序列不為空，則將它的中間元素與目標(biāo)數(shù)值進(jìn)行比較，判斷是否相等；

（3）若相等，則返回中間元素索引，并退出算法；此時(shí)已查找成功。

（4）若不相等，則比較中間元素與目標(biāo)數(shù)值的大??；

（5）若中間元素 > 目標(biāo)數(shù)值，則將當(dāng)前序列的前半部分作為新的待查序列；

（6）若中間元素 < 目標(biāo)數(shù)值，則將當(dāng)前序列的后半部分作為新的待查序列；

（7）在新的序列上重新從第（1）步開(kāi)始查找。

四、以在升序序列中查找目標(biāo)元素為例，二分查找算法的實(shí)現(xiàn)思路是：

（1）初始狀態(tài)下，將整個(gè)序列作為搜索區(qū)域（假設(shè)為 [B, E]）；

（2）找到搜索區(qū)域內(nèi)的中間元素（假設(shè)所在位置為 M），和目標(biāo)元素進(jìn)行比對(duì)。如果相等，則搜索成功；如果中間元素大于目標(biāo)元素，表明目標(biāo)元素位于中間元素的左側(cè)，將 [B, M-1] 作為新的搜素區(qū)域；反之，若中間元素小于目標(biāo)元素，表明目標(biāo)元素位于中間元素的右側(cè)，將 [M+1, E] 作為新的搜素區(qū)域；

（3）重復(fù)執(zhí)行第二步，直至找到目標(biāo)元素。如果搜索區(qū)域無(wú)法再縮小，且區(qū)域內(nèi)不包含任何元素，表明整個(gè)序列中沒(méi)有目標(biāo)元素，查找失敗。

五、實(shí)例講解

在下圖所示的升序序列中查找元素 31。

二分查找算法的具體實(shí)現(xiàn)過(guò)程為：

（1）初始狀態(tài)下，搜索區(qū)域是整個(gè)序列。找到搜索區(qū)域內(nèi)的中間元素。指定區(qū)域內(nèi)中間元素的位置可以套用如下公式求出：

Mid = ? Begin + (End - Begin) / 2 ?

End 表示搜索區(qū)域內(nèi)最后一個(gè)元素所在位置，Begin 表示搜索區(qū)域內(nèi)第一個(gè)元素所在的位置，Mid 表示中間元素所在的位置。

所有元素的位置分別用 0~9 表示，中間元素的位置為 ? 0 + (9 - 0) / 2 ? = 4，如下圖所示：

中間元素 27 < 31，可以斷定 [0, 4] 區(qū)域內(nèi)絕對(duì)沒(méi)有 31，目標(biāo)元素只可能位于 [5, 9] 區(qū)域內(nèi)，如下圖所示：

（2）在 [5, 9] 區(qū)域內(nèi)，中間元素的位置為 ? 5 + (9 - 5) / 2 ? = 7，如下圖所示：

中間元素 35 > 31，可以斷定 [7, 9] 區(qū)域內(nèi)絕對(duì)沒(méi)有 31，目標(biāo)元素只可能位于 [5,6] 中，如下圖所示：

（3）在 [5, 6] 區(qū)域內(nèi)，中間元素的位置為 ? 5 + (6- 5) / 2 ? = 5，中間元素就是 31，成功找到目標(biāo)元素。

六、代碼展示

（1）如下是用二分查找算法在 {10, 14, 19, 26, 27, 31, 33, 35, 42, 44} 升序序列中查找元素 31 的 C 語(yǔ)言程序：

#include <stdio.h>
//實(shí)現(xiàn)二分查找算法，ele 表示要查找的目標(biāo)元素，[p,q] 指定查找區(qū)域
int binary_search(int *arr,int p,int q,int ele) {
    int mid = 0;
    //如果[p,q] 不存在，返回 -1
    if (p > q) {
        return -1;
    }
    // 找到中間元素所在的位置
    mid = p + (q - p) / 2;
    //遞歸的出口
    if (ele == arr[mid]) {
        return mid;
    }
    //比較 ele 和 arr[mid] 的值，縮小 ele 可能存在的區(qū)域
    if (ele < arr[mid]) {
        //新的搜索區(qū)域?yàn)?nbsp;[p,mid-1]
        return binary_search(arr, p, mid - 1, ele);
    }
    else {
        //新的搜索區(qū)域?yàn)?nbsp;[mid+1,q]
        return binary_search(arr, mid + 1, q, ele);
    }
}

int main()
{
    int arr[10] = { 10,14,19,26,27,31,33,35,42,44 };
    //輸出二叉查找元素 31 所在位置的下標(biāo)
    printf("%d", binary_search(arr, 0, 9, 31));
    return 0;
}

（2）如下是用二分查找算法在 {10, 14, 19, 26, 27, 31, 33, 35, 42, 44} 升序序列中查找元素 31 的 Java 程序：

public class Demo {
    // 實(shí)現(xiàn)二分查找算法，ele 表示要查找的目標(biāo)元素，[p,q] 指定查找區(qū)域
    public static int binary_search(int[] arr, int p, int q, int ele) {
        // 如果[p,q] 不存在，返回 -1
        if (p > q) {
            return -1;
        }
        // 找到中間元素所在的位置
        int mid = p + (q - p) / 2;
        // 遞歸的出口
        if (ele == arr[mid]) {
            return mid;
        }
        // 比較 ele 和 arr[mid] 的值，縮小 ele 可能存在的區(qū)域
        if (ele < arr[mid]) {
            // 新的搜索區(qū)域?yàn)?nbsp;[p,mid-1]
            return binary_search(arr, p, mid - 1, ele);
        } else {
            // 新的搜索區(qū)域?yàn)?nbsp;[mid+1,q]
            return binary_search(arr, mid + 1, q, ele);
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[] { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44 };
        // 輸出二叉查找元素 31 所在位置的下標(biāo)
        int add = binary_search(arr, 0, 9, 31);
        System.out.print(add);
    }
}

（3）如下是用二分查找算法在 {10, 14, 19, 26, 27, 31, 33, 35, 42, 44} 升序序列中查找元素 31 的 Python 程序：

#實(shí)現(xiàn)二分查找算法，ele 表示要查找的目標(biāo)元素，[p,q] 指定查找區(qū)域
def binary_search(arr,p,q,ele):
    #如果[p,q] 不存在，返回 -1
    if p > q:
        return -1
    #找到中間元素所在的位置
    mid = p + int( (q - p) / 2 )
    #遞歸的出口
    if ele == arr[mid]:
        return mid
    #比較 ele 和 arr[mid] 的值，縮小 ele 可能存在的區(qū)域
    if ele < arr[mid]:
        return binary_search(arr,p,mid-1,ele)
    else:
        return binary_search(arr,mid+1,q,ele)

arr = [10, 14, 19, 26, 27, 31, 33, 35, 42, 44]
#輸出二叉查找元素 31 所在位置的下標(biāo)
add = binary_search(arr, 0, 9, 31);
print(add)

以上程序的輸出結(jié)果均為：

5