Java – 算法 – 二分查找

简介

二分查找法，应用在一段具有有序的数组中进行查找。

二分查找原理

二分查找是指，我们把一段有序的数组，设置查找的开头和结尾，先取中间的值，和需要查找的值进行对比，如果这个值比数组中间值大，那么我们可以认为，这个值的索引位置，位于中间之右，如果值比数组中间的值小，那们可以认为，这个值的索引在中间之左，我们可以通过改变开头索引和结尾索引，来快速缩小查找范围，但这种方法只适用于具有顺序特性的数组上。

1.min和max表示当前要查找的范围

2.mid是在min和max中间的

3.如果要查找的元素在mid的左边，缩小范围时，min不变，max等于mid减1

4.如果要查找的元素在mid的右边，缩小范围时，max不变，min等于mid加1

二分查找实现

private static int binarySearch(int[] arr, int num) {

        // 设定一个开始索引min
        int min = 0;
        // 设定一个结束索引max
        int max = arr.length;

        // 当min 小于 max的时候，说明还有区间需要计算，否则就是超出数组区间
        while (min <= max) {
            // 取得它们中间的索引值
            int mid = (min + max) / 2;
            if (arr[mid] < num) {
                // 如果中间的值 小于 num 的值，说明 num 在中间之右
                // 在中间之右的话，我们就把min的值等于mid+1
                min = mid + 1;
            } else if (arr[mid] > num) {
                // 如果中间的值 大于 num 的值，说明 num 在中间之左
                // 在中间之左的话，我们就把max的值等于mid-1
                max = mid - 1;
            } else {
                // 如果即不大于，也不小于，说明已找到，mid索引的值就是num
                return mid;
            }
        }

        return -1;
    }

二分查找改进算法

通过一个等式

mid = min + ( key-arr( min ) ) / ( arr[ max ] - arr[ min ] ) * ( max - min )

可以更容易得出 mid 的值更接近查找值，数组顺序越是顺，这个等式查找出来的 mid 就越精确。