【算法学习系列】06 - 利用二分法查找有序数组中的某个数 num

二分法

说明

二分法是一种常用的算法，也称为折半查找或二分查找。它适用于已经有序的数组中，通过将数组从中间划分成两个部分，每次根据目标值与中间值的大小比较来确定下一步的查找范围，直到找到目标值或者确定不存在为止。

二分法的时间复杂度为 O(log n)，较低的时间复杂度让它成为了解决大规模数据搜索效率较高的算法之一。

实现

根据说明，二分法实现代码如下：

	// 二分法：从有序数组 arr 中找到 num
    private boolean findNum(int[] arr, int num){
        if (arr == null || arr.length == 0){
            return false;
        }
        // 示例 [1, 2, 3, 4, 5, 5, 8]
        int L = 0,R = arr.length - 1;
        while (L <= R){
            int middle = (L + R) / 2;
            if (arr[middle] == num){
                return true;
            }else if (arr[middle] < num){
                L = middle + 1;
            }else {
                R = middle - 1;
            }
        }
        return false;
    }

二分法验证

下面会使用对数器来进行验证。如果不了解对数器的同学可以先阅读 【算法学习系列】05 - 对数器的说明与使用 一文了解对数器的相关知识。

实现暴力算法

暴力算法 B 能保证结果肯定正确，但是不保证时间复杂度或者是执行效率，主要是用来跟实现的算法 A 进行结果比对。

实现代码如下：

	// 暴力算法，保证算法结果肯定正确
    private boolean test(int[] sortedArr, int num){
        for (int value : sortedArr){
            if (value == num){
                return true;
            }
        }
        return false;
    }

• 返回值为 true 表示有序数组 sortedArr 中存在 num
• 返回值为 false 表示有序数组 sortedArr 中不存在 num

对数器使用

验证算法的测试代码实现如下：

	private void testFindNum(){
        int maxLen = 10;
        int maxValue = 1000;
        int testCount = 100000;
        boolean isCorrect = true;

        for (int i = 0;i < testCount;i++){
            // 生成随机长度和随机值的数组
            int[] randomArr =  createRandomArr(maxLen, maxValue);
            // 进行选择排序
            SortUtil.selectionSort(randomArr);
            // 随机生成一个数 num
            int num = (int)((maxValue + 1) * Math.random()) - (int)(maxValue * Math.random());
            // 跟暴力算法 test(int[] sortedArr, int num) 的值进行比对
            if (test(randomArr, num) != findNum(randomArr, num)){
                isCorrect = false;
                break;
            }
        }

        System.out.println(isCorrect ? ":> 算法正确!" : ":> 算法出错了!");
    }

这里进行了十万次随机样本测试。

首先随机生成一个无序数组 randomArr ，然后对 randomArr 进行选择排序，保证其有序；再随机生成一个数 num。

然后使用有序数组 randomArr 和 num 分别给到自己实现的算法 A 和暴力算法 B 当做输入，并进行两个算法的输出结果比对。

如果在大样本随机下，二者比对结果都一致，说明实现的二分算法正确；反之则说明算法不正确。

注：上面涉及的排序算法和随机数组生成函数请阅读【算法学习系列】05 - 对数器的说明与使用 一文查看。

验证结果

运行程序，输出结果如下图示：

• 由上图打印可知，二分算法验证正确。

“Peace Love Respect”