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

* 常规二分法的时间复杂度，O(logN)。 * O(log2N)，即log以2为底，N的对数。 *

* 一次砍一半，一次砍一半，一次砍一半。 * 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; } }