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

思路

(1) 暴力法：从数组的第一个元素开始顺序查找，直到找到numbers[i] > numbers[i+1]的情况，此时numbers[i+1]就是最小的元素。

(2) 二分法：讲解如下：

代码实现

 1 class Solution {
 2 public:
 3     int minArray(vector<int>& numbers) {
 4         int numbersSize = numbers.size();
 5         int left, right, mid;
 6         left = 0;
 7         right = numbersSize-1;
 8 
 9         while(left <= right) {
10             mid = left + (right-left) / 2 ;
11             if(numbers[mid] > numbers[right])
12                 left = mid + 1;
13             else if(numbers[mid] < numbers[right])
14                 right = mid;   //注意这里不能等于mid-1
15             else
16                 --right;
17         }
18 
19         return numbers[left];
20     }
21 };

复杂度分析

参考

力扣官方题解 - 旋转数组的最小数字