本节介绍二分查找的相关内容。

        给定一个已经排好序的数组，如何快速从中找出值为x的元素的位置?
        一个通俗的做法是从第一个数开始遍历数组，直到找到x。时间复杂度O(n)。这种方法在数据量很大又频繁查找时效率低下。
为了充分利用数据的有序性，可以使用二分查找算法在O(logn)复杂度下快速找到特定值的元素位置。二分查找是用来在已排序序列中找到特定值元素位置的高效算法，它的原理是一个基本事实:

在升序序列中[l，r]中，若mid=(l+r)/2且value[mid]<x，那么x对应的元素必位于(mid，r]中，否则必位于[l，mid]中。降序排列类似。

        对于一个升序排序，不难写出代码:

1
2
3
4
5
6
int binary_find(int l, int r, int x) {
    if (l == r)return l;
    int mid = (l + r) / 2;
    if (value[mid] < x)return binary_find(mid + 1, r, x);
    else return binary_find(l, mid, x);
}

        但是，假定在[2，3]中寻找元素x，value[2] < x，value[3]=x，运行这段代码，会发现函数无限递归导致段错误。这是因为(2+3)/2=2，函数不断地在[2，3]中查找，无法跳出这个循环。这也是这种二分查找算法的重要缺陷。那么如何优化?
        当函数传入参数l，r时，规定函数只能在(l，r]中查找，那么代码就变成:
1
2
3
4
5
6
7
int binary_find(int l, int r, int x)//(,]
{
    if (r == l + 1)return r;
    int mid = (l + r) / 2;
    if (value[mid] < x)return binary_find(mid, r, x);
    else return binary_find(l, mid, x);
}

        这时调用函数binary_find(-1，n-1，x)即可(n为数据量)。这种半开半闭式二分查找思想可以完美解决上面的问题。