Find Minimum in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

思路：如果中间节点的值最大，则取后半部分，如果中间节点的值最小，则取前半部分。

C++实现代码如下：（采用二分法的方法，注意边界的处理）

#include<iostream> #include<vector> using namespace std;class Solution { public:int findMin(vector<int> &num){if(num.empty())return 0;int s=0;int t=num.size()-1;if(num[s]<num[t])return num[s];while(s<t){int mid=(s+t)/2;if(num[mid]<num[t])t=mid;elses=mid+1;}return num[s];} };int main() {Solution s;vector<int> num={4,5,6,7,8,9,0,1,2,3};cout<<s.findMin(num)<<endl; }

 

总结

以上是生活随笔为你收集整理的Find Minimum in Rotated Sorted Array的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。