在本教程中，我们将看到如何在数组中找到局部最小值。

问题

如果元素的值小于其邻居，则元素是局部最小值。

int [] arr = {10, 5, 3, 6, 13, 16, 7};
Output: 2

int [] arr = {11,12,13,14};输出：11

int [] arr = {10};输出：10

int [] arr = {8,6};输出：6

解决方案

天真的方法

我们可以使用循环和比较邻居元素，我们将获得局部最小值。
最糟糕的复杂性将是

o(n)。

更有效的方法

我们可以使用二进制搜索来查找局部最小值。

最坏的情况复杂性将是

o(log n)。
这是简单的算法

• 找出 mid元素
• 如果 mid元素是 less比邻居都要返回它。
• 如果 mid元素是 greater比它的左邻居，然后离开
• 否则走向。

package org.igi.theitroad;
public class LocalMinima {
 
	public int findLocalMinima(int [] arr, int start, int end){
 
		/*find the mid index*/
		int mid = start + (end-start)/2;
		int size = arr.length;
 
		/*check the local minima 
		 *first check if left and right neighbor exists */
		if((mid==0 || arr[mid-1]>arr[mid]) &&
				(mid==size-1 || arr[mid+1]>arr[mid]))
			return arr[mid];
		/* check if left neighbor is less than mid element, if yes go left */
		else if(mid>0 && arr[mid]>arr[mid-1]){
			return findLocalMinima(arr, start, mid);
		}
		else { 
			/*check if right neighbor is greater than mid element, if yes go right */
			return findLocalMinima(arr, mid+1, end);
		}
	}
 
 
	public static void main(String[] args) {
		LocalMinima l = new LocalMinima();
		int [] arr = {10, 5, 3, 6, 13, 16, 7};
		System.out.println("Local Minima is: " + l.findLocalMinima(arr,0,arr.length));
	}
}

运行上面的程序时，我们将得到以下输出。

局部最小值是：3