东营建设信息网老网站营销方案策划书

链接：

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

154. 寻找旋转排序数组中的最小值 II

题意：

找一个数组里的最小值，这个数组是有非递减数组旋转而来的，旋转n次表示把前n个数移动到数组末尾

解：

很有趣的二分，由于是非递减数组旋转而来，所以最小值往右一定小于等于最小值左侧，可以以此进行二分

如果这个数字大于nums[r]，那么他一定属于最小值左侧，小于nums[r]一定属于右侧

But：唯一要注意等于的情况，因为存在重复数字，所以有可能 所有/大部分数字都是同一个，则时候无法判断在最小值左侧还是右侧，只能减小右端点。也不能和左端点比较/增大左端点，因为有可能是旋转n次转回了原数组（前面一段一个是个非递减序列，一开始的L=0算是前面一段的最小值）

一边是Easy一边是Hard是吧，真有你的嗷leetcode（大概是暴力能过的原因=-=）

实际代码：

#include<bits/stdc++.h>
using namespace std;
int findMin(vector<int>& numbers)
{int lg=numbers.size(),l=0,r=lg-1;while(l<r){int mid=l+((r-l)>>1);if(numbers[mid]==numbers[r]) r--;else if(numbers[mid]<numbers[r]) r=mid;else l=mid+1;}return numbers[l];
}
int minArray(vector<int>& numbers)
{int lg=numbers.size(),l=0,r=lg-1;while(l<r){int mid=l+((r-l)>>1);if(numbers[mid]==numbers[r]) r--;else if(numbers[mid]<numbers[r]) r=mid;else l=mid+1;}return numbers[l];
}
int main()
{vector<int> numbers;int num;while(cin>>num) numbers.push_back(num);int ans=minArray(numbers);cout<<ans<<endl;return 0;
}

限制：

• n == numbers.length
• 1 <= n <= 5000
• -5000 <= numbers[i] <= 5000
• numbers 原来是一个升序排序的数组，并进行了 1 至 n 次旋转