二分法

说明

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

二分法的时间复杂度为 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 ? ":> 算法正确!" : ":> 算法出错了!");
    }