- /*
- 题目:
- 把一个数组最开始的若干个元素搬到数组末尾, 我们称之为数组的旋转.
- 输入一个递增排序的数组的旋转, 输出旋转数组中的最小元素.
- */
- /*
- 思路:
- 采用二分的方法, 旋转数组实质上是上左半部分为递减数组, 右半部分为递增数组.
- 取中间元素 mid, 若大于等于最右端的元素, 则说明 mid 在左半部分, 则 low=mid+1;
- 若小于最右端的元素, 则说明 mid 在右半部分, 则 high = mid;
- */
- int minNumberInRotateArray(vector<int> rotateArray) {
- int length = rotateArray.size();
- if( length== 0 ) return 0;
- int low = 0, high = length - 1, mid = 0;
- while(low <high){
- mid = low + ((high - low)>> 2);
- if(rotateArray[mid]>= rotateArray[high]){
- low = mid + 1;
- }else if(rotateArray[mid] < rotateArray[high]){
- high = mid;
- }
- }
- return rotateArray[low];
- }
来源: http://www.bubuko.com/infodetail-3282045.html