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

二分查找法

对一个已排序数组进行查找，查找方法是每次取数组中间位置的数和当前查找数比较，如果查找数等于当前这个中间数，则找到结果直接返回（这里不考虑数组中有多个相同的查找数的情况，后续章节会讲解）。查找数小于中间数，则去中间数左侧继续查找，查找数大于中间数，则去中间数右侧查找，不管继续在左侧查找还是右侧查找，都重复以上操作，直到找到结果或发现数组中不存在查找数。

上面写的不直观，我们举个例子，例如当前数组：{1,2,5,6,7,8,9,15,22,26,36}

数组已经排序了，我们要查找值为22的数，按照逻辑，我们取数组中间位置的数和查找数进行比较，数组中间数为下标为5的数，值为8，8<22，则从下标6到数组结束的区间，继续取中间位置的比较。

这里有高低位的概念，从下标为5之后的元素到数组结尾继续取中间数，那么低位下标是6，高位下标为10，我们取中间数下标为：low+(high-low)/2=8，下标为8的值刚好是22，那么查找结束，返回值为8。

代码：

public static void main(String[] args) {
        int[] arrs = {1,2,5,6,7,8,9,15,22,26,36};
        System.out.println("查找数的下标为:"+ search(arrs, 22));
    }

    public static int search(int[] arrs, int x) {
        int low = 0, high = arrs.length-1;
        while(low<=high) {
            //不使用(low+high)/2，是因为low+high有可能溢出
            int mid = low+(high-low)/2;
            if(arrs[mid] == x) {
                return mid;
            }
            //这里的的low和high的复制如果直接复制mid，
            //可能造成死循环，当查询的值不在数组中，就永远无法终止循环
            if(arrs[mid] > x) {
                high = mid-1;
            }
            if(arrs[mid] < x) {
                low = mid+1;
            }
        }
        return -1;
    }

输出：

查找数的下标为:8

二分查找法的时间复杂度O(logn)。

但是二分查找是有使用条件的。
1、查找的数据结构必须是数组，因为通过高低位计算快速定位到中间位置，所以如果使用链表，原来的O(1)复杂度找到中间位置，就变成了O(n)，时间复杂度就不是O(logn)了。
2、查找的数组必须是已经排序的有序数组，如果数组是无序的，则需要先排序。
3、二分查找不适用于数据量过大的场景，因为二分查找基于数组，数组那么久需要内存中一段连续的空间，如果数据量过大，那么就需要非常大的连续内存空间，例如一个二分查找需要1g的连续内存，当前系统有2g内存，但是连续内存不足1g，那么就无法使用二分查找。