本文共 1400 字，大约阅读时间需要 4 分钟。

剑指Offer 11.旋转数组的最小数字

简单法： 遍历数组，找到第一个左边的数大于右边，就返回右边的数，时间复杂度O(n)。

class Solution {    public int minArray(int[] numbers) {       for(int i = 0; i < numbers.length-1; i++)       {           if(numbers[i] > numbers[i+1])  return numbers[i+1];       }       return numbers[0];    }}

二分法：

时间复杂度O(logn)，最差的时候为O(n) 声明 i, j 双指针分别指向 numbers 数组左右两端；m为i，j中点，当i<j时，判断 numbers[m]和numbers[j]的大小。分三种情况： if(numbers[m] < numbers[j]) //说明m在右排序数组中，旋转点在左边 j = m; else if(numbers[m] > numbers[j]) //说明m在左排序数组中，旋转点在右边 i = m + 1; //旋转点一定会在右排序数组中，所以i=m+1，免得多比较一个数 else if(numbers[m] == numbers[j]) //无法判断m在哪个数组中 j = j - 1; 第三种情况可能会错过旋转点，但是还是能返回与旋转点值相同的点 代码：

class Solution {    public int minArray(int[] numbers) {      int i,j,m;      i = 0;      j = numbers.length-1;      m = (i + j) / 2;      while(i < j) {         if(numbers[m] < numbers[j]) //说明m在右排序数组中，旋转点在左边         j = m;        else if(numbers[m] > numbers[j]) //说明m在左排序数组中，旋转点在右边         i = m + 1;        else if(numbers[m] == numbers[j]) //无法判断m在哪个数组中          j = j - 1;           m = (i + j) / 2;      }      return numbers[i];    }}

---

二刷

之前没有深刻理解当nums[j] == nums[mid]时，为什么j–一定是正确的。二刷时甚至忘记了当nums[j] == nums[mid]时，无法判断旋转点在哪一边。比如：3,3，3,3，3,4，5,3，3这个数组，第一次nums[mid] = 3,nums[j] = 3, 此时无法判断旋转点位置，j–，nums[mid] = 3,j会一直减到i的位置停下，返回nums[i],此时nums[i]虽然不是旋转点，但是与旋转点的值一定相同，因为左右都是递增序列。

这里总结一下：

1、左闭右闭区间，i = m + 1,j = m - 1,当i>j的时候停止. 2、左闭右开区间，i = m + 1， j = m，当i = j 的时候停止

转载地址：http://grim.baihongyu.com/