二分查找

局部最小问题

思路来源

一周刷爆LeetCode，算法大神左神（左程云）耗时100天打造算法与数据结构基础

笔记内容

• 问题描述：

  对于一个数组，相邻值不等。查找出该数组中满足局部最小的值。

  局部最小：

  1. x[0]<x[1] 2
  2. x[n-1]<x[n-2]
  3. x[i-1]>x[i] && x[i+1]>x[i]

• 算法思路：

  1. 首先检测首尾是否满足局部最小，若满足则查找成功，退出算法；
  2. 若均不满足，则在数组首部为局部下降，在尾部为局部上升，数组中必存在一个拐点满足局部最小，使用二分法查找。
  3. 对于查找段，首先判断mid是否满足条件，满足则直接返回，结束算法。
  4. 若判断不满足局部最小条件，则继续进行二分，通过判断下一二分查找段两端是否满足必存在拐点的条件，选择其中一段进行查找。

public class LocalMinimum {
    /**
     * 二分查找
     * 局部最小
     * */
    public static void main(String[] args) {
        int[] target = {7,6,3,2,7};
        int length = target.length;
        //首尾判断
        if(target[0]<target[1]){
            System.out.println(target[0]);
        }else if(target[length-1]<target[length-2]){
            System.out.println(target[0]);
        }else {
            getResult(target,0,length-1);
        }
    }

    public static void getResult(int[] target,int left,int right){
        int mid = left+(right-left)/2;
        if(target[mid]<target[mid+1] && target[mid]<target[mid-1]){
            System.out.println(target[mid]);
            return;
        }
       if(target[mid]<target[mid+1] && target[left]> target[left+1]){
           getResult(target,left,mid);
       }
        if(target[mid]>target[mid+1] && target[right]> target[right-1]){
            getResult(target,mid,right);
        }
    }
}