关于快速查找法（折半/二分查找法）解释（一次记住）binarysearch

全栈程序员-用户IM • 2021年5月12日下午8:00 • 未分类

简单说就是折半再折半，很内容理解。

目的：看一次，永远记住。（妈妈再也不用担心我不会写查找了）

难点：low,high操作。

    @Test
    public void binarySearch() {
        //数组一定要是顺序的。
        double arr[] = {0.0, 0.001, 0.1, 0.2, 0.3, 0.4, 0.5, 1.0, 2.0, 3.0}
        double key = 0.3;
        int low = 0;
        int high = arr.length - 1;

        while (low <= high) {
            int mid = (low + high) / 2;
            double midVal = arr[mid];

            if (key > midVal)//大在high区，把low往上抬，砍掉low区
                low = mid + 1;
            else if (key < midVal)//小在low区，把high往下压，砍掉high区
                high = mid - 1;
            else {
                System.out.println(key + "的位置是" + mid); 
                return;//--------找到了退出
            }
        }

        System.out.println(-(low + 1));//没找到，返回负数
    }

当key大于的midVal的时候说明key在high区

low区的数据就放弃了，怎么放弃low区？直接把最low的位置指到mid的位置就行了，但还不够，还要多移一位才行(low=mid+1)。

这样取值的区间就变成high区的了mid+1的位置到high。然后再折半。这时可能跑过头了，再往回跑（high=mid-1）就行了。

只要记住key在高区就把low往上抬，key在低区就把high往下压就行了。（为什么要mid+1或者-1，不直接等于mid？因为mid已经和key比较过了）

核心就是解决low，high的操作，理解了这个操作，快速查找就不是问题。

简单粗暴

如图：其实就是排除法，不停的干掉区域，通过不停移动low和high的位置，收缩范围，最后找到。

关于快速查找法（折半/二分查找法）解释（一次记住）binarysearch