526互联

局部最小问题（二分查找）

发布时间 2023-12-19 11:18:47作者: Noule

二分查找

局部最小问题

  • 问题描述：

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

    局部最小：

    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);
        }
    }
}