对数器验证算法正确性----bug寻找,文章中含有测试源码
**
先写一个随机数组生成函数再写一个暴力求解函数再写一个二分法函数循环打印,产生任意随机数组,验证暴力求解和二分法求解是否一致,一致则正确,不一致则错误,打印出错误例子方便后面寻找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!"); }}**## 验证算法正确**
代码来源于B站,侵权请联系删除