题目描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
解法一：从头到尾将数组遍历一次，找到最小的元素。时间复杂度O(n)
解法二：二分查找。最小的元素是前后两个有序子数组的分界线。注：需要考虑特殊情况，即数组两边都一样大。
代码如下：
#include<iostream>using namespace std;int binarySearch(int a[], int start, int end){ if(start+1==end || start==end) { int smaller = a[end] < a[start] ? a[end] : a[start]; return smaller; } int mid=(start+end)/2; if(a[start]==a[end] && a[mid]==a[end]) //特殊情况：两边都一样大，两边均遍历 { int find1=binarySearch(a,start,mid); int find2=binarySearch(a,mid+1,end); return find1 < find2 ? find1 : find2; } else if(a[mid]>=a[start] && a[mid]>a[end]) binarySearch(a,mid,end); else binarySearch(a,start,mid); }int main(){ int N,min=1000001; int a[10000]; cin>>N; for(int i=0;i<N;i++) cin>>a[i]; cout<<binarySearch(a,0,N-1)<<endl; return 0;}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/162923.html
