外包类设计网站/百度指数分析案例

原题链接

注意：直接遍历数组复杂度为O(N)不符合题目要求

基础分析

观察样例数组旋转后，数组可以看作两个排序后的子数组，而前面数组的元素都大于第二个数组。其中最小值正好位于两个数组的分界线，可以联想到二分法查找

一个指针指向数组的开始，一个指针指向数组的结束。第三个数组指向中间元素（begin+end)/2

根据二分思想如果arr[mid]对应的数字小于等于arr[end]，说明其在第二个数组中，让end=mid。如果arr[mid]大于等于arr[begin]说明其在第一个数组中，begin=mid。

特殊样例分析

1.输入数组为空或数组大小为1

在开始函数中需要判断数组大小，当大小为1时返回此元素即可

2.旋转了0个元素，即数组还是有序的。

此时最小元素为第一个元素。所以我们让mid的初值为begin（0）
当arr[begin]>=arr[end]时说明旋转元素>0在执行二分

3.因为重复元素导致无法区分中值是在那个数组的情况

代码实现

#include<assert.h>
class Solution {
public:int FindMin(vector<int>&arr)//顺序查找{int min=arr[0];for(int i=0;i<arr.size();i++){if(arr[i]<min){min=arr[i];}}return min;}int minNumberInRotateArray(vector<int> rotateArray) {assert(!rotateArray.empty());if(rotateArray.size()==1){return rotateArray[0];}int begin=0;int end=rotateArray.size()-1;int mid=begin;//让mid刚开始=beginwhile(rotateArray[begin]>=rotateArray[end])//当不满足while情况时//说明数组没有旋转直接返回mid下标对应的数组的值{if(end-begin==1){mid=end;break;}mid=(end+begin)/2;//当mid对应值个前后相同时，只能通过顺序查找if(rotateArray[begin]==rotateArray[mid]&&rotateArray[mid]==rotateArray[end]){return FindMin(rotateArray);}if(rotateArray[mid]>=rotateArray[begin]){begin=mid;}if(rotateArray[mid]<=rotateArray[end]){end=mid;}}return rotateArray[mid];}
};