数据结构与算法——二分查找

1. 二分查找的思想

二分查找是一种使用十分普遍的查找算法，其基本的思路也非常的简单，在一个有序的数据集合中，我们想要查找某个数据，直接取最中间的那个数据，将它和要找的数据进行比较，如果较大，则在更大的那个数值区间继续取中间值查找，反之亦然。

例如我们要在一个有序的集合里[1，3，5，6，7，8，10]，查找5这个值，那么二分查找的过程就如下图所示，经过三次查找操作就能够找到。

2. 二分查找的实现

相信你已经能够理解二分查找的思路了，接下来看看它的代码实现。其实根据思路不难看出，二分查找有点分治的思想，所以代码可以用递归实现，也可以用循环实现。

二分查找的递归实现：

public class BinarySearch {

    public static int binarySearchByRecursion(int[] data, int value) {
        return binarySearchInternally(data, 0, data.length - 1, value);
    }

    private static int binarySearchInternally(int[] data, int low, int high, int value) {
        while (low <= high){
            //计算中间值
            int mid = low + ((high - low) >> 1);

            if (data[mid] == value) return mid;
            else if (data[mid] < value) return binarySearchInternally(data, mid + 1, high, value);
            else return binarySearchInternally(data, low, mid - 1, value);
        }
        return -1;
    }
}

二分查找循环实现：

public static int binarySearchByCircle(int[] data, int value) {
        int low = 0;
        int high = data.length - 1;

        while (low <= high){
            //计算中间值
            int mid = low + ((high - low) >> 1);
            if (data[mid] == value) return mid;
            else if (data[mid] < value) low = mid + 1;
            else high = mid - 1;
        }
        return -1;
    }

3. 二分查找的局限性

二分查找是一种很高效的算法，时间复杂度为 O(logn)，要是使用上的话，非常的方便。但是，二分查找对数据的要求也十分严苛。

首先，二分查找只适用于顺序表结构，说简单点，就是数组。因为可以利用数组下标访问的特性，快速取出数据进行比较。其他的数据结构例如链表，如果使用二分查找的话，不能进行下标访问，每次比较都必须遍历链表寻找中间节点，时间复杂度就很高了。

其次，二分查找针对的是有序数组，如果数据未排序，则必须进行排序才能够使用，前面说到了，排序的时间复杂度一般为 O(nlogn)。所以，二分查找较适用于一次排序，多次查找的数据。如果数据的插入和删除操作过于频繁，那么维护有序的成本就很高。

最后，二分查找适用于数据量较大的场景，假如我们要在几十或者几百个数据中进行查找，那直接遍历查找即可。面对大量的数据，二分查找方能体现其优势。