概述：二分搜索（英语：binary search），也称折半搜索（英语：half-interval search）、对数搜索（英语：logarithmic search），是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

二分查找

二分查找

分类 数据结构 时间复杂度 最优时间复杂度 平均时间复杂度 空间复杂度
搜索算法 数组 O(log n) О(1) O(log n) 迭代：O(1), 递归：O(log n)

代码范例

C语言

// 递归版本
int binary_search(const int arr[], int start, int end, int khey) {
    if (start > end)
        return -1;

    int mid = start + (end - start) / 2; //直接平均可能會溢位，所以用此算法
    if (arr[mid] > khey)
        return binary_search(arr, start, mid - 1, khey);
    if (arr[mid] < khey)
        return binary_search(arr, mid + 1, end, khey);
    return mid; //最後檢測相等是因為多數搜尋狀況不是大於要不就小於
}
// while循环
int binary_search(const int arr[], int start, int end, int khey) {
    int mid;
    while (start <= end) {
        mid = start + (end - start) / 2; //直接平均可能會溢位，所以用此算法
        if (arr[mid] < khey)
            start = mid + 1;
        else if (arr[mid] > khey)
            end = mid - 1;
        else
            return mid; //最後檢測相等是因為多數搜尋狀況不是大於要不就小於
    }
    return -1;
}

Python

def binary_search(arr,start,end,hkey):
    if start > end:
        return -1
    mid = start + (end - start) / 2
    if arr[mid] > hkey:
        return binary_search(arr, start, mid - 1, hkey)
    if arr[mid] < hkey:
        return binary_search(arr, mid + 1, end, hkey)
    return mid

JavaScript

Array.prototype.binary_search = function(low, high, khey) {
    if (low > high)
        return -1;
    var mid = parseInt((high + low) / 2);
    if (this[mid] > khey)
        return this.binary_search(low, mid - 1, khey);
    if (this[mid] < khey)
        return this.binary_search(mid + 1, high, khey);
    return mid;
};

复杂度分析

时间复杂度
折半搜索每次把搜索区域减少一半，时间复杂度为O(log n)。（n代表集合中元素的个数）
空间复杂度
О(1)。虽以递归形式定义，但是尾递归，可改写为循环。

参考：https://zh.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%90%9C%E7%B4%A2%E7%AE%97%E6%B3%95