【算法&数据结构初阶篇】：二分查找解决局部最小值问题

Love The Way You Lie 2024-03-29 15:20 67阅读 0赞

> 先解释下局部最小值问题，这么理解，比如有一个数组，**数组中如果某个局部区域存在一个最小值，那么我们就将这个值给返回**即可。那么现在可以先记住这个现象，如果数组前两个元素是下行状态，意思即arr\[0\]>arr\[1\]，而倒数两个元素是上行状态，arr\[arr.length - 1\] > arr\[arr.length - 2\] ，那么肯定在0 - arr.length-1中，即整个数组存在一个局部最小，道理很简单，**一开始数组往下走，最后是往上走，那其中肯定会存在至少一个局部最小**，可以想象连绵不绝的山脉，上下跌宕的感觉，或者是股票，你懂的了。因为存在一边最小，所以我们可以采用二分查找算法来进行处理，也印证了二分查找不一定需要有序数组，在某一限制条件下如存在局部最小值，只要一边有最小，那么我们就可用二分，还要一个注意点，就是数组虽然不要求有序，但是**任意相邻的两个元素不等**。

**目录**

一、思路分析

二、代码演示

三、边界考虑

--------------------

## 一、思路分析 ##

下面我们先做个思路分析，看看有多少种情况：

1.  当**arr\[0\] < arr\[1\]**时：即可以表示arr\[0\]就是局部最小，因为右元素大于他，没有左元素，这种特殊情况，可以表示arr\[0\]为局部最小，直接返回
2.  当**arr\[N - 1\] < arr\[N - 2\]**时：即可以表示arr\[N - 1\]就是局部最小，因为左元素大于他，没有右元素，这种特殊情况，可以表示arr\[N - 1\]为局部最小，直接返回
3.  如果没有以上两种情况，那么说明arr\[0,N-1\]中必然存在局部最小，**因为此时arr\[0\] > arr\[1\],arr\[N - 1\] > arr\[N - 2\] ，头部下行，尾部上行，过程必然存在一个局部最小，才能在尾部上行。**

## 二、代码演示 ##

package class03;
    
    public class Code04_BSAwesome {
    
    	// arr 相邻的数不相等！ 局部最小值问题 找一个局部最小值 有则返回
    	public static int oneMinIndex(int[] arr) {
    		if (arr == null || arr.length == 0) {
    			return -1;
    		}
    		int N = arr.length;
    		if (N == 1) {
    			return 0;
    		}
    		//特殊边界：第一位小于第二位 表示第一位就是局部最小直接返回
    		if (arr[0] < arr[1]) {
    			return 0;
    		}
    		//特殊边界：倒数第一位小于倒数第二位 表示倒数第一位就是局部最小直接返回
    		if (arr[N - 1] < arr[N - 2]) {
    			return N - 1;
    		}
    		int L = 0;
    		int R = N - 1;
    
    		/*
    		程序走到这里 说明前面没有符合的特殊情况 那么L...R 肯定有局部最小， 二分查找进行查询。
    		注意这里的边界判断，局部最小值我们确保L,MID,是三个数，而避免左右边界与MIN重叠，重叠的话
    		会导致下面的判断会存在越界，因为我们每次都会将MID 与其+1  -1的左右元素比较，所以要保证L-R
    		有三个数，那就是L , R-1 , R  L要小于 R-1  这样遍历就会保证有三个数，如果退出了里面没有找
    		到局部最小，表示只剩两个元素，那我们就跳出，最后返回时判断L与R那个小，则返回哪个元素即可
    		比如这个例子： [3,2,3,2,3] 假设while(L <= R) 第一轮二分 arr[2]=arr[mid],没有局部最小，
    		判断arr[1] < arr[mid] 右边界左移到arr[mid - 1] 那此时arr[L]=arr[0],arr[R]=arr[1],接着
    		第二轮二分，mid=arr[0],与arr[L]重叠，接着判断mid的左元素时，arr[mid - 1] = arr[0 - 1]越界，
    		所以就不能按L<=R来循环就是这个道理，需要有三个值，不重叠
    		 */
    		while (L < R - 1) {
    			int mid = (L + R) / 2;
    			// 比如 arr[3] > arr[4] < arr[5] 表示为一组最小值，arr[4]即为局部最小值 直接返回
    			if (arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]) {
    				return mid;
    			} else {
    				//如果上面没有找到，则接着判断如果arr[4] 大于 arr[3]说明左边是下行状态，左边肯定存在一个局部最小值，移动右边界
    				//先左还是右都一样，只要能找到一边有局部最小即可
    				if (arr[mid] > arr[mid - 1]) {
    					R = mid - 1;
    				} else {
    					//否则则说明 arr[4] > arr[5]，右边下行状态，所以左边肯定右局部最小，移动左边界
    					L = mid + 1;
    				}
    			}
    		}
    		//走到这里说明L-R区间只有两个数。最后返回时判断L与R那个小，则返回哪个元素即可
    		return arr[L] < arr[R] ? L : R;
    	}
    
    	// 生成随机数组，且相邻数不相等
    	public static int[] randomArray(int maxLen, int maxValue) {
    		int len = (int) (Math.random() * maxLen);
    		int[] arr = new int[len];
    		if (len > 0) {
    			arr[0] = (int) (Math.random() * maxValue);
    			for (int i = 1; i < len; i++) {
    				do {
    					arr[i] = (int) (Math.random() * maxValue);
    				} while (arr[i] == arr[i - 1]);
    			}
    		}
    		return arr;
    	}
    
    	// 也用于测试
    	public static boolean check(int[] arr, int minIndex) {
    		if (arr.length == 0) {
    			return minIndex == -1;
    		}
    		//定义min最小值的左元素与右元素索引，用来判断是否是局部最小
    		int left = minIndex - 1;
    		int right = minIndex + 1;
    		//如果左边元素在边界内，则需要左边界 > min,才能表示min局部最小，如果越界，说明是第一个元素为min，返回true
    		boolean leftBigger = left >= 0 ? arr[left] > arr[minIndex] : true;
    		//如果右边元素在边界内，则需要右边界 > min,才能表示min局部最小，如果越界，说明是最后个元素为min，返回true
    		boolean rightBigger = right < arr.length ? arr[right] > arr[minIndex] : true;
    		//左边边界都为true，则才是最小局部值
    		return leftBigger && rightBigger;
    	}
    
    	public static void printArray(int[] arr) {
    		for (int num : arr) {
    			System.out.print(num + " ");
    		}
    		System.out.println();
    	}
    
    	public static void main(String[] args) {
    		int maxLen = 100;
    		int maxValue = 200;
    		int testTime = 1000000;
    		System.out.println("测试开始");
    		for (int i = 0; i < testTime; i++) {
    			int[] arr = randomArray(maxLen, maxValue);
    			int ans = oneMinIndex(arr);
    			if (!check(arr, ans)) {
    				printArray(arr);
    				System.out.println(ans);
    				break;
    			}
    		}
    		System.out.println("测试结束");
    
    	}
    
    }

## 三、边界考虑 ##

>  *  这里的难点细节在于对while循环二分查找时的边界考虑，while(L < R-1) ，注意是考虑我们二分时会判断中间值mid与左元素、右元素的大小，避免越界，L , R , mid 是不能重叠的，重叠的话，表示没有左元素或没有右元素，此时再进行左右元素比较，那肯定就越界报错。所以就需要L , R-1 ,R 至少左中右三个元素，所以条件判断就是 L < R-1进行二分查询，L >= R-1则退出，这是一点
>  *  如果二分找到，则会存在 arr\[L\] > arr\[mid\] < arr\[R\],即局部最小元素下标 return mid。没有找到呢，说明最后只剩L,R两个元素，那么我们最后程序结束前，就只需判断这两个元素谁小，谁小则返回谁