(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.
class Solution {
public:
int findMin(vector
int low = 0;
int n = nums.size();
int high = n-1;
while(low
{
int mid = low + (high-low)/2;
//notes the index
if(nums[mid]>nums[high]) low = mid+1; //left sorted,search in right part
else if(nums[mid]
return nums[low];
}
};
if there is duplicates in the rotated sorted array.
class Solution {
public:
int findMin(vector
int low = 0;
int n = nums.size();
int high = n-1;
while(low
{
int mid = low + (high-low)/2;
//notes the index
if(nums[mid]>nums[high]) low = mid+1; //right sorted
else if(nums[mid]
}
return nums[low];
}
};
search insert position
class Solution {
public:
int searchInsert(vector
int low = 0;
int n = nums.size();
int high = n-1;
while(low
int mid = low + (high-low)/2;
//notes the index
if(nums[mid]
high = mid; //right sorted,search in left part
}
return nums[low]
};
No comments:
Post a Comment