查找算法（一）二分查找

二分查找（Binary Search）算法，也称折半查找算法，类似分治思想。
二分查找针对一个有序的数据集合，每次都通过跟区间的中间元素对比，将待查找的区间范围缩小至之前的一半，直至找到要查找的元素，或者区间范围被缩小为0。

复杂度分析

二分查找的时间复杂度为O(log n)，虽然二分查找的时间负责度为O(log n)，但是比很多O(1)的速度都要快，因为O(1)可能标示一个非常大的数值，如O(1000)。

局限性分析

• 二分查找依赖数组结构
  二分查找需要利用下标随机访问元素，使用链表等其他数据结构无法使用二分查找；
• 二分查找针对有序数据
  二分查找需要有序的数据，如果数据无序则首先需要排序，排序的时间复杂度最低是O(n log n)。所以如果针对一组静态数据，没有频繁插入、删除场景，可以进行一次排序、多次二分查找，将排序成本均摊。如果数据存在频繁插入、删除场景，则每次执行二分查找前都要先进行排序，成本很高。所以，二分查找最好用在插入、删除频率低，一次排序多次查找的场景中。
• 数据量太小不适合二分查找
  数据量很小时顺序遍历即可。
• 数据量太大不适合二分查找
  二分查找底层依赖数组结构，数组需要一段连续的存储空间，数据太大时可能使用的不是连续存储数据结构。

Java 代码实现

1. 循环实现

    public static int binarySearch(int[] data, int target) {
        int low = 0;
        int high = data.length - 1;
        int middle = 0;
        // low > high：说明data为空
        if (low > high || target < data[low] || target > data[high]) {
            return -1;
        }
        while (low <= high) {
            middle = (low + high) / 2;
            if (data[middle] > target) {
                high = middle - 1;
            } else if (data[middle] < target) {
                low = middle + 1;
            } else {
                return middle;
            }
        }
        return -1;
    }

2. 递归实现

    public static int recursiveBinarySearch(int[] data, int target, int low, int high) {
        if (low > high || target < data[low] || target > data[high]) {
            return -1;
        }
        int middle = (low + high) / 2;
        if (data[middle] > target) {
            return recursiveBinarySearch(data, target, low, middle - 1);
        } else if (data[middle] < target) {
            return recursiveBinarySearch(data, target, middle + 1, high);
        } else {
            return middle;
        }
    }