对数器验证算法正确性----bug寻找，文章中含有测试源码

港控/mmm° 2023-10-02 17:51 10阅读 0赞

\*\*

先写一个随机数组生成函数
    再写一个暴力求解函数
    再写一个二分法函数
    循环打印，产生任意随机数组，验证暴力求解和二分法求解是否一致，一致则正确，不一致则错误，打印出错误例子方便后面寻找bug
    [打印出错误例子](https://editor.csdn.net/md?articleId=122718241)

\*\*

package cn.Text;
    
    import java.util.Arrays;
    
    /**
     * 二分法
     * 一次找一半，比较找位置/数字（num）   保证有序
     * 注：我们中点位置一般去上中点
     * 135679      上中点为5
     */
    public class Dichotomy {
        
        /**
         *  二分法查找
         */
    
        public static boolean find(int[] arr,int num){
        
            //TODO 边界条件,先剔除掉不符合条件的一部分
            if((arr==null)||(arr.length==0)){
        
                return false;
            }
            //TODO 左边界
            int L=0;
            //TODO 有边界
            int R=arr.length-1;
            /**
             * arr的[L...........R]之间查找一个数num
             */
            while(L<=R){
        
                int media=(L+R)/2;
                if(arr[media]==num){
        
                    return true;
                }
                else if(arr[media]<num){
        
                    L=media+1;
                }
                else{
        
                    R=media-1;
                }
            }
            return false;
        }
    
        /**
         * 遍历，暴力求解
         * @param sortedArr
         * @param num
         * @return
         */
        public static boolean test(int[] sortedArr, int num) {
        
            for (int cur : sortedArr) {
        
                if (cur == num) {
        
                    return true;
                }
            }
            return false;
        }
        /**
         * 生成一个随机数组
         */
    
        public static int[] generateRandomArray(int maxSize, int maxValue) {
        
            int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
            for (int i = 0; i < arr.length; i++) {
        
                //TODO 最后减去一个(int) (maxValue * Math.random())是为了产生复数的测试集合，
                //         例如不减(int) (maxValue * Math.random())之前数组是  1，15，2，33，9
                //             减去(int) (maxValue * Math.random())之后数组是  -31，5，7，23，-11
                //             产生负数，增加测试机效果，减少耦合性
                arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
                /** TODO int 取整     int(8.9)=8     int(1.2)=1  int(0.9)=0
                 * 上面的（maxValue+1）是应为数字全部扩大maxValue倍，为什么不是maxValue呢
                 * int(9.9)=9  ,   Math.random的取值范围是[0,1),左闭右开，举个例子说明一下
                 *  TODO  maxValue=9，Math.random()=0.99【因为范围为[0,1),左闭右开，故不能到1，只能无限趋近于1】
                 *  int((maxValue) * Math.random())=int(9*0.99)=int(8.91)=8,
                 *  TODO  maxValue=1，Math.random()=0.99
                 *  int((maxValue) * Math.random())=int(1*0.99)=0
                 *  所以maxValue要加1
                 *  int((maxValue+1) * Math.random())=int(2*0.99)=1
                 */
            }
            return arr;
        }
    
        /**
         * 主函数
         *
         * @param args
         */
        public static void main(String[] args) {
        
            int testTime = 500000;
            int maxSize = 10;
            int maxValue = 100;
            boolean succeed = true;
            for (int i = 0; i < testTime; i++) {
        
                int[] arr = generateRandomArray(maxSize, maxValue);
                //TODO 打印出随机生成的数组，循环一次生成一个
                System.out.println(Arrays.toString(arr));
                //TODO 因为二分法的先决条件是数组有序，所以我们来个排序使数组从小到大排序
                Arrays.sort(arr);
                //TODO 排列后的数组
                System.out.println(Arrays.toString(arr));
                int value = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
                //TODO 二分法和暴力法进行比对，看是否一样
                if (test(arr, value) != find(arr, value)) {
        
                    System.out.println("出错了！");
                    succeed = false;
                    break;
                }
            }
            System.out.println(succeed ? "Nice!" : "Fucking fucked!");
        }
    }
    **
    
    ## 验证算法正确
    
    **

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiN6Imv5L2_size_20_color_FFFFFF_t_70_g_se_x_16]

**代码来源于B站，侵权请联系删除**

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiN6Imv5L2_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/228f42ffba84481293be4e8400ddab0f.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LiN6Imv5L2_,size_20,color_FFFFFF,t_70,g_se,x_16