【知识积累】查找数组中的局部最小值（数组中的值不相等）

package com.example.demo.algorithm;

/**
 * @Description :
 * 局部最小值问题 -> 所有值不相等
 *
 * 1) 0 位置  如果小于1位置 那么直接返回0位置
 * 2) N-1 位置 如果小于N-2位置 那么直接返回N-1位置
 * 3) i位置  0↓ N-1↑ 那0~N-1范围有一个局部最小
 *    二分来到中间位置
 *    判断mid是否大于mid-1位置  0↓ mid↑ 则0~mid范围有一个局部最小
 *    判断mid是否大于mid+1位置 mid↓ N-1↑ 则则mid~N-1范围有一个局部最小
 *    如都不满足 说明 mid小于mid-1位置的数且小于mid+1位置的数 直接返回
 *
 * @Author : Darren
 * @Date : 2021 年 02 月 07 日 20:06:18
 * @since : 1.0
 */
public class J007_BSPartLeast {

    public static void main(String[] args) {
        int count = 20;
        int maxSize = 100;
        int maxValue = 100;
        for (int i = 0; i < count; i++) {
            int[] arrays = J001_SelectSort.generateRandomArray(maxSize, maxValue);
            J001_SelectSort.printArray(arrays);
            int result = bsPartLeast(arrays);
            System.out.println(result);
        }
    }

    public static int bsPartLeast(int[] arrays){
        if (arrays == null || arrays.length == 0){
            return -1;
        }

        if (arrays.length == 1 || arrays[0] < arrays[1]){
            return arrays[0];
        }

        if (arrays[arrays.length-1] < arrays[arrays.length-2]){
            return arrays[arrays.length-1];
        }
        int l = 1;
        int r = arrays.length - 2;
        int mid = 0;
        while (l < r){
            mid = l + ((r - l) >> 1);
            if (arrays[mid] > arrays[mid-1]){
                r = mid - 1;
            }else if (arrays[mid] > arrays[mid + 1]){
                l = mid + 1;
            }else{
                return mid;
            }
        }
        return l;
    }
}

 

本文地址：https://blog.csdn.net/axin1240101543/article/details/113757956