目录

• 前言
• 问题介绍
• 解决方案
• 代码编写
• • java语言版本
  • c语言版本
  • c++语言版本
• 思考感悟
• 写在最后

前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识！

问题介绍

原问题
给定一个数组，已知数组中所有值都不相等，求数组的局部最小值（取一个即可）。
局部最小值：如果arr[i]满足 arr[i] < arr[i+1] 并且 arr[i] < arr[i-1] ，则表示arr[i]为局部最小值

解决方案

原问题：
1、首先判断特殊情况：
· 数组长度是否为1，如果只有一个值，直接返回
· 数组长度是否为2，如果是，则谁小返回谁
· 数组两端是否时局部最小，即 arr[0]是否小于arr[1],arr[len-1] < arr[len-2]，如果存在直接返回
2、如果特殊情况都没有返回，则为普通情况且数组开头为递减且结束为递增，形象点：\…/，那么中间一定存在一个转折点（因为没有相同值）。二分法获取中间值，由于arr数组中不存在相同的值，因此不需要判断arr[i]是否与前后值相同，对于每一个arr[mid]有以下几种情况
· arr[mid] < arr[mid+1] && arr[mid] < arr[mid-1] ，直接返回即可
· arr[mid] < arr[mid + 1] && arr[mid] > arr[mid-1] ，这种情况说明mid在递增序列上，说明左（递减）到中（递增）之间一定存在最小值，因此 right = mid-1
· arr[mid] > arr[mid+1] && arr[mid] < arr[mid-1],这种情况说明mid在递减序列上，说明右（递增）到中（递减）之间一定存在最小值，因此 left = mid+1

代码编写

java语言版本

原问题：
方法一:

    /*** 二轮测试：返回局部最小值* 返回一个极小值即可* @param arr* @return*/public static int getLessIndexCp1(int[] arr) {if (arr == null || arr.length == 0) {throw new RuntimeException("arr is invalid");}// 先判断头尾是否最小值if (arr.length == 1 || arr[0] < arr[1]) {return arr[0];}else if (arr[arr.length-1] < arr[arr.length-2]) {return arr[arr.length-1];}else {// 开始计算极小值int left = 1;int right = arr.length-2;while (left < right) {// 前中位数int mid = (left + right)/2;if (arr[mid+1] < arr[mid]) {// 递减 在mid和right之间left = mid+1;}else if (arr[mid-1] < arr[mid]){// 递增right = mid-1;}else {// 两个都不符合说明当前值就是极小值return mid;}}return left;}}public static void main(String[] args) {System.out.println(getLessIndexCp1(new int[]{6,5,7,8,4,3,9}));}

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

高中的极小值知识，比较简单，但是需要注意边界值和特殊情况，理清楚还是需要些时间的，还有就是二分法的熟练度，二分法刚开始非常容易死循环，这里需要注意mid值的判断。

写在最后

方案和代码仅提供学习和思考使用，切勿随意滥用！如有错误和不合理的地方，务必批评指正~
如果需要git源码可邮件给2260755767@qq.com
再次感谢左大神对我算法的指点迷津！