ZIP06已知一个有序数组arr，和一个数字num 返回数组中是否含有这个数字 (使用二分法).zip 1.19KB

weixin_44259230

资源文件列表:

06已知一个有序数组arr，和一个数字num。返回数组中是否含有这个数字。(使用二分法).zip 大约有1个文件
  1. 06.txt 2.66KB

资源介绍:

已知一个有序数组arr，和一个数字num。返回数组中是否含有这个数字。(使用二分法)
package class01; import java.util.Arrays; /** * 二分法 * 已知一个有序数组arr，和一个数字num。返回数组中是否含有这个数字。(使用二分法) * <p> * 常规二分法的时间复杂度，O(logN)。 * O(log2N)，即log以2为底，N的对数。 * <p> * 一次砍一半，一次砍一半，一次砍一半。 * N个数，一共砍几次呢？一共砍了O(log2N)次，每砍一次，看一眼这个中点上的数，是O(1)的。 * 所以就是log2N乘以1，还是O(log2N)。 */ public class Code04_BSExist { public static void main(String[] args) { //当写while (L < R)时，是错误的，反例如下。正确的写法是while (L <= R)。 //-24 -21 -19 -13 -10 -8 0 7 10 10 20 //int[] arr = {-24, -21, -19, -13, -10, -8, 0, 7, 10, 10, 20}; int maxSize = 30; int maxValue = 30; int testTimes = 10; int num = 7; boolean flag = true; for (int i = 0; i < testTimes; i++) { int[] arr = generateRandomArray(maxSize, maxValue); Arrays.sort(arr); printArr(arr); System.out.println(num); boolean b = exist(arr, num); System.out.println(b); System.out.println("---"); boolean test = test(arr, num); if (b != test) { flag = false; break; } } System.out.println(flag ? "nice!" : "oops!"); } public static boolean exist(int[] sortedArr, int num) { int L = 0; int R = sortedArr.length - 1; while (L <= R) { int mid = L + ((R - L) >> 1);//必须要加括号，否则会先算加法，导致死循环。 if (sortedArr[mid] < num) { L = mid + 1; } else if (sortedArr[mid] > num) { R = mid - 1; } else { 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++) { arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random()); } return arr; } public static void printArr(int[] arr) { for (int i : arr) { System.out.print(i + " "); } System.out.println(); } public static boolean test(int[] arr, int num) { for (int i : arr) { if (i == num) { return true; } } return false; } }
100+评论
captcha
    相关资源
    类型标题大小时间
    ZIPi2pinstall_0.9.18_windows (1).zip14.01MB8月前
    ZIPbugreport-2024-07-30-203317.zip63.1MB8月前
    ZIP【浏览器插件】Instapaper.zip170.85KB8月前
    ZIP【浏览器插件】Octotree GitHub code tree.zip3.55MB8月前
    ZIP概述：先将i指向第二个数(索引为1)，将j指向i-1位置，如果j大于等于0，并且arrj>arrj+1，将将arrj1.12KB8月前
    ZIPorangefox-cepheus-stable@r11.0_3.zip48.75MB8月前
    ZIPhaxm-windows-v7-8-0.zip496.52KB8月前
    ZIP计组ppt计组ppt计组ppt计组ppt40.19MB8月前