package com.cowain.test; /** * @Author: fxw * @Date: 2022/2/26 22:13 */ public class Code3 { //有一个数组无序 并且 相邻不相等 找到局部最小的值 public static int find(int[] array) { if (array == null || array.length == 0) { return -1; } int N = array.length; //当数组长度为1是 直接返回当前元素为最小值 if (N == 1) { return 0; } //当左边界L<L+1时 直接返回L if (array[0] < array[1]) { return 0; } //当右边界R-1<R-2时 直接返回R-1 if (array[N - 2] > array[N - 1]) { return N - 1; } //以下情况就是长度大于1并且边界条件不满足 int L = 0; int R = N - 1; //防止越界处理 L < R-1 即最后只会剩下两个数 while (L < R - 1) { int mid = (L + R) / 2; //先是二分法找到中间值 假如 中间值的左边和右边都比他大 那么直接返回中间值 if (array[mid - 1] > array[mid] && array[mid] < array[mid + 1]) { return mid; } else { //当出现else情况中时 会出现以下三种情况 // 1 array[mid-1]<array[mid]&&array[mid+1]>array[mid] // 1 array[mid-1]>array[mid]&&array[mid]>array[mid+1] // 1 array[mid-1]<array[mid]&&array[mid+1]>array[mid] if (array[mid] > array[mid - 1]) {//认为0-mid-1中必定有最小值 砍掉mid-R R = mid - 1; } else {//认为mid-mid-1中必定有最小值 砍掉L-mid L = mid + 1; } } } return array[L] > array[R] ? R : L; } //生成随机数组 无序 并且 相邻不相等 public static int[] createRandomArray(int randomIndex, int randomValue) { int[] randomArray = new int[(int) (Math.random() * randomIndex)]; if (randomArray.length > 0) {//判断长度 randomArray[0] = (int) (Math.random() * randomValue);//给第一个元素复制 for (int i = 1; i < randomArray.length; i++) { do { randomArray[i] = (int) (Math.random() * randomValue); } while (randomArray[i] == randomArray[i - 1]);//如果相邻的两个数相等 那么就重新赋值 } } return randomArray; } //编写测试验证方法 public static boolean check(int[] array, int minIndex) { if (array.length == 0 || array == null) { return minIndex == -1; //返回false } int L = minIndex - 1; int R = minIndex + 1; boolean leftBigger = L > 0 ? array[L] > array[minIndex] : true; boolean RightBigger = R < array.length ? array[R] > array[minIndex] : true; return leftBigger && RightBigger; } //打印数组函数 public static void printArray(int[] array) { for (int value : array) { System.out.print(value + ","); } System.out.println(); } public static void main(String[] args) { int maxLen = 15; int maxValue = 200; int testTime = 1000000; System.out.println("测试开始"); for (int i = 0; i < testTime; i++) { int[] arr = createRandomArray(maxLen, maxValue); int ans = find(arr); if (!check(arr, ans)) { printArray(arr); System.out.println(ans); break; } } System.out.println("测试结束"); } }