蓝桥杯练习：旋转数组的最小数字（改造二分法）

蓝桥杯练习：旋转数组的最小数字（改造二分法）

旋转数组的最小数字（改造二分法）

​​题目​​​​思路​​​​代码​​

题目

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1，2，3，4，5}的一个旋转，该数组的最小值为1.

思路

第一个思路：最简单的是直接顺序查找，那么复杂度是O(n)；

第二个思路：看到题目“递增排序的数组”，那么我们利用这一特性，类似二分法，不断的减少，复杂度是O(log2 n）。 分析旋转数组，发现，前面的元素旋转到后面，则最小值总是在最大值的右边。 用while循环，终止条件是begin+1

代码

这是第二个思路的代码

public class Main { public static void main(String[] args) { // TODO Auto-generated method stub int [] arr= {5,1,2,3,4}; int res =min(arr); System.out.println(res); } static int min(int[] arr) { int begin =0; int end=arr.length-1; //考虑没有旋转这种特殊的旋转 if(arr[begin]>1);// >>1实际上就相当于除2 //要么左侧有序，要么右侧有序； if(arr[mid]>=arr[begin]) { begin=mid; }else { end=mid; } } return arr[end]; }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。