二分查找

数据顺序存储，有序序列 O(logn)

递归实现二分查找：

    public static int binarySearch(int[] data, int x, int low, int high) {
        if (low > high) {
            return -1;
        }

        int mid = low + (high - low) >> 1;
        if (data[mid] == x) {
            return mid;
        } else if (data[mid] > x) {
            return binarySearch(data, x, low, mid - 1);
        } else {
            return binarySearch(data, x, mid + 1, high);
        }
    }

非递归实现二分查找：

public static int binarySearch(int[] data, int x) {
        int low = 0, high = data.length - 1;
        while (low <= high) {
            int center = low + (high - low) >> 1;
            if (data[center] > x) {
                high = center - 1;
            } else if (data[center] < x) {
                low = center + 1;
            } else {
                return center;
            }
        }

        return -1;
    }