# Search in Rotated Sorted Array II

2017-05-10

Search in Rotated Sorted Array II。

# Search in Rotated Sorted Array II

```/*
Description:
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).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array

Follow up for ”Search in Rotated Sorted Array”: What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array
*/

/*
Parse:二分查找，难度主要在于左右边界的确定。

note:没有重复的元素是重要信息

-若A[m]>=A[l]，则区间[l,m]一定递增
-若A[m]==A[l]确定不了，那就l++,往下看一步即可。

*/

// LeetCode, Search in Rotated Sorted Array II
// 时间复杂度 O(n)空间复杂度(1)
#include
#include
using namespace std;
class Solution {
public:
bool search(const vector& nums, int target) {
int first = 0, last = nums.size();
while (first != last) {
const int mid = first + (last - first) / 2;
if (nums[mid] == target) {
return true;
}

if (nums[first] < nums[mid]) {
if (nums[first] <= target && target < nums[mid]) {
last = mid;
}
else {
first = mid + 1;
}
}

else if (nums[first] > nums[mid]) {
if (nums[mid] < target && target <= nums[last-1]) {
first = mid + 1;
}
else {
last = mid;
}
}

else {
//skip duplicate one
first++;
}
}

return false;
}

};

int main(){
Solution a;
vector nums;
nums.push_back(0);  nums.push_back(1);  nums.push_back(2);  nums.push_back(4);
nums.push_back(5);  nums.push_back(5);  nums.push_back(6);  nums.push_back(7);

int b=a.search(nums,1);
cout<

```