09局部最小问题.zip

* 对于一个数组，使用二分法的前提，一定是这个数组整体有序吗？ * 答：不是。局部最小问题就是反例。 */ public class Code07_BSAwesome { public static int getLessIndex(int[] arr) { if (arr == null || arr.length == 0) { return -1; } if (arr.length == 1 || arr[0] < arr[1]) { return 0; } if (arr[arr.length - 1] < arr[arr.length - 2]) { return arr.length - 1; } int L = 1; int R = arr.length - 2; while (L <= R) { int mid = L + ((R - L) >> 1); if (arr[mid] > arr[mid - 1]) { R = mid - 1; } else if (arr[mid] > arr[mid + 1]) { L = mid + 1; } else { return mid; } } System.out.println("==============================="); return L; } public static void main(String[] args) { int maxSize = 50; int maxValue = 30; int testTimes = 10000; boolean flag = true; for (int i = 0; i < testTimes; i++) { int[] arr1 = generateRandomArr2(maxSize, maxValue); int num = getLessIndex(arr1); if (!test(arr1, num)) { printArr(arr1); for (int index = 0; index < arr1.length; index++) { System.out.print(index + "\t"); } System.out.println(); System.out.println("num = " + num); flag = false; break; } } //至少打印一次 int[] arr1 = generateRandomArr2(maxSize, maxValue); printArr(arr1); for (int index = 0; index < arr1.length; index++) { System.out.print(index + "\t"); } System.out.println(); int num = getLessIndex(arr1); System.out.println("num = " + num); System.out.println(flag ? "nice!" : "oops!"); } public static int[] generateRandomArr(int maxSize, int maxValue) { int[] arr = new int[(int) (Math.random() * maxSize)]; for (int i = 0; i < arr.length; i++) { arr[i] = (int) (Math.random() * maxValue) - (int) (Math.random() * maxValue); } return arr; } public static void printArr(int[] arr) { for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + "\t"); } System.out.println(); } //生成的随机数组中的数字，相邻不相等。 public static int[] generateRandomArr2(int maxSize, int maxValue) { int[] arr = new int[(int) (Math.random() * maxSize) + 1]; arr[0] = (int) (Math.random() * maxValue) - (int) (Math.random() * maxValue); for (int i = 1; i < arr.length; i++) { do { arr[i] = (int) (Math.random() * maxValue) - (int) (Math.random() * maxValue); } while (arr[i] == arr[i - 1]); } return arr; } //用于测试，num位置的数，是不是局部最小。 public static boolean test(int[] arr, int num) { if (arr.length <= 1) { return true; } if (num == 0) { return arr[0] < arr[1]; } if (num == arr.length - 1) { return arr[num] < arr[num - 1]; } return (arr[num] < arr[num - 1] && arr[num] < arr[num + 1]); } }