# 153.Find Minimum in Rotated Sorted Array

## August 17, 2016

153.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.

/*solution1*/
class Solution {
public:
int findMin(vector<int>& nums) {
int size=nums.size();
int i=0,min=0;
for(i=0;i<size;i++){
if(nums[i]<nums[min])
min=i;
}
return nums[min];
}
};

1. [0,1,2,3,4,5,6,7]这种情况的特征是最左边的值小于最右边，所以最左边的一定是minimum，直接返回。
2. [4,5,6,7,0,1,2,3]这种情况的特征是中间的数大于最右边的数，所以minimum一定出现在右半区中，调整到右半区继续查找。
3. [5,6,7,0,1,2,3,4]这种情况的特征是中间的数小于最左边的数，所以minimum一定出现在左半区中，调整到右半区继续查找。 代码如下:
/*solution2*/
class Solution {
public:
int findMin(vector<int>& nums) {
int size=nums.size(),low=0,high=size-1,mid=0;
while(low<high){
if(nums[low]<nums[high])
return nums[low];
mid=(low+high)/2;
if(nums[mid]>nums[high])
low=mid+1;
else
high=mid;
}
return nums[low];
}
};

### 学籍管理系统文档

#### 北邮教务系统评教脚本

Published on September 17, 2017

#### 72.Edit distance

Published on September 17, 2017