二分查找

思想

在一个有序的数据集合中，每次都通过跟区间的中间元素进行比较，将待查找的区间缩小为之前的一半，直到找到指定元素，或者区间被缩小为0。

示例

public boolean isExist(int[] data, int left, int right, int target) {
    if (left > right) return false;
    // 注意中点下标计算，避免数据溢出
    int middle = (right - left) / 2 + left;
    if (target > data[middle]) {
        return isExist(data, middle + 1, right, target);
    } else if (target < data[middle]) {
        return isExist(data, left, middle - 1, target);
    } else {
        return true;
    }
}

时间复杂度

O(logn)