折半（二分）查找

---

问题描述##

折半查找

思路##

明显的解法是从左到右扫描数据，其运行花费的是线性时间。然而，这个算法没有用到该表已经排序的事实，这就使得算法可能不是最好的。一个好的策略是验证X是否是居中元素。如果是，则答案就找到了。如果X小于居中元素，那么我们可以应用同样的策略于居中元素左边已经排好序的子序列；同理，如果X大于居中元素，那么我们检查数据的右半部分。

代码##

    public static <AnyType extends Comparable<? super AnyType>> int binarySearch(AnyType[] a, AnyType x) {
        int low = 0, high = a.length - 1;

        while (low <= high) {
            int mid = (low + high) / 2;
            if (a[mid].compareTo(x) < 0) {
                low = mid + 1;
            } else if (a[mid].compareTo(x) > 0) {
                high = mid - 1;
            } else {
                return mid;
            }
        }

        return -1;
    }

分析##

根据上面的算法，二分查找的过程可以用二叉判定树来描述。例如，有序表{44,45,47,50,65,70}的二叉判定树如下图所示：

二叉判定树
在二分查找过程中，查找失败时需要比较的关键字至多为log2(N+1)向上取整（二叉树的层数），查找成功时需要比较的关键字至多为log2(N+1)向上取整。二分查找的时间复杂度为O（log2N）。二分查找的平均性能和最坏性能相当接近。其优点是查找效率比顺序查找高，缺点是要求查找有序表，并且二分查找只适用于顺序存储结构，链式存储结构的顺序表无法采用二分查找算法。

二分查找提供了在O(logN)时间内的contains操作，但是所有其他操作（特别是insert操作）均需要O(N)时间。在数据稳定（即不允许插入操作和删除操作）的应用中，这种操作可能是非常有用的。此时输入数据需要一次排序，但是此后的访问会很快。有个例子是一个程序，它需要保留（产生于化学和物理领域的）元素周期表的信息。这个表是相对稳定的，因为很少会引入新元素。元素名可以始终是排序的。由于大约只有110种元素，因此找出一个元素最多需要8次。但是执行顺序查询就需要多得多的查找次数。