二分查找

本文主要回顾二分查找，主要有如下内容：

二分查找
二分查找的非递归实现
二分查找的递归实现

PS:本文仅回顾最基本的二分查找，其实二分查找还有许多其他变形，详细的可以参考文末的参考资料。

查找问题是计算机中最基本最朴素的问题，也非常重要。我们知道要在一个数组中查找一个元素，直接遍历的办法，其时间复杂度为O(n)。那么有没有更快的办法呢？
答案是有的，使用二分查找，但是二分查找的使用是有条件的，那便是要求查找的数组或者序列是有序的。
注意有些地方又把二分查找叫折半查找或者二分搜索。

二分查找的非递归实现

清单1：二分查找的非递归实现

using namespace std;
// 二分查找法,在有序数组arr中,查找target
// 如果找到target,返回相应的索引index
// 如果没有找到target,返回-1
template<typename T>
int binarySearch(T a[], int n, T target)
{
    int l = 0;
    int r = n-1;
    //在[l, r]中查找
    while(l <= r)
    {
        // 防止极端情况下的整形溢出，使用下面的逻辑求出mid
        int mid = l+(r-l)/2;
        if(target < a[mid])
        {
            r = mid-1;
        }
        else if(target > a[mid])
        {
            l = mid+1;
        }
        else
        {
            return mid;
        }
    }

    //没有找到target，返回-1
    return -1;
}

二分查找的递归实现

清单2 二分查找的递归实现

template<typename T>
int __binarySearch(T a[], int l, int r, T target)
{
    if(l > r)
    {
        return -1;
    }

    int mid = l+(r-l)/2;
    if(target == a[mid])
    {
        return mid;
    }
    else if(target < a[mid])
    {
        return __binarySearch(a, l, mid-1, target);
    }
    else
    {
        return __binarySearch(a, mid+1, r, target);
    }
}

template<typename T>
int binarySearchR(T a[], int n, T target)
{
    __binarySearch(a, 0, n-1, target);
}

二分查找的非递归版本性能上会比递归版本好一些（常数级别的差异）。
递归优点：代码简洁清晰，可读性更好
递归可读性好这一点，对于初学者可能会反对。实际上递归的代码更清晰，但是从学习的角度要理解递归真正发生的什么，是如何调用的，调用层次和路线，调用堆栈中保存了什么，可能是不容易。但是不可否认递归的代码更简洁。一般来说，一个人可能很容易的写出前中后序的二叉树遍历的递归算法，要写出相应的非递归算法就比较考验水平了，恐怕至少一半的人搞不定。所以说递归代码更简洁明了。
递归缺点：由于递归需要系统堆栈，所以空间消耗要比非递归代码要大。而且，如果递归深度太大，系统堆栈可能耗尽，导致程序崩溃。

参考资料

[算法（第4版）]
你真的会写二分查找吗？