剑指Offer06 旋转数组的最小数字

剑指Offer06: 旋转数组的最小数字

题意

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组[3,4,5,1,2]为[1,2,3,4,5]的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

思路

根据旋转数组的定义，其实旋转数组实质上就是两个非递减的序列组合而成，前一个序列不小于后一个序列，因此寻找旋转数组中的最小值就是寻找两个序列的分界点，即出现array[i+1] < array[i]的位置（其实应该算上等于，因为极端数据可能所有数字均一样。。。）

1、直接暴力：循环求解出现array[i+1] < array[i]的位置，输出array[i+1]，可以AC,但是时间复杂度O(n),不建议。

2、二分求解：首先将left = 0, right = len(array) - 1, mid = (left + right) / 2, 然后比较 array[left]与 array[mid]的大小,当left与right不相等时：

array[left] < array[mid]，说明分界点在mid上或其右侧，令left = mid, right保持不动array[left] > array[mid]，说明分界点在mid上或其左侧，令right = mid, left保持不动array[left] == array[mid], 说明当前可能数字一致或者left和right相差1，left++

代码

class Solution { public: int minNumberInRotateArray(vector<int> rotateArray) { int len = rotateArray.size(); if(len == 0) return 0; else if(len == 1) return rotateArray[0]; int left = 0, right = len - 1; while(left != right){ int mid = (left + right) / 2; if(rotateArray[mid] > rotateArray[left]){ //mid > left 说明分界点在mid右侧 left = mid; }else if(rotateArray[mid] < rotateArray[left]){ //mid < right说明在左侧 right = mid; }else{ left++; } } return rotateArray[left]; } };

反思

​ 写二分要特别注意终止条件与更新策略，比如若是没有left++操作，可以回一直困在left+1 = right中无法前进。