欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-07-06 15:02:21
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范围有一个局部最小 * ....
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

相关标签: 算法