题目
剑指 Offer 11. 旋转数组的最小数字
题目概述:
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转,该数组的最小值为1。
示例
基础框架
class Solution { public int minArray(int[] numbers) { } }
解题思路
由于题目所给的是递增排序的数组,所以利用二分法求解【查找要求:①顺序存储(通过下标就可以得到关键字) ②元素有序(任取一个关键字的值就可以确定所寻找的值是在前面还是后面)】
class Solution{ public int minArray(int[] numbers){ int left=0; int right=numbers.length-1; while(left<right){ int mid=left+(right-left)/2;//取中点,防止right和left太大时直接相加导致溢出 if(numbers[mid]<numbers[right]){//后半部分一定顺序,分界点在mid左边 right=mid; } else if(numbers[mid]>numbers[right]){//前半部分一定顺序,分界点在mid右边 left=mid+1; } else{ //number[mid]==numbers[right]无法二分,暴力缩小范围 right--; } } return numbers[left]; } }