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.
这个和前面的一个不一样就在于可能会有重复的数字，那么判断的时候就应该注意了，遇到start<=mid的不一定说明当前的区间[start, mid]就是递增的。这时候就应该++来确认下，代码如下：
1 // LeetCode, Search in Rotated Sorted Array II 2 // 时间复杂度O(n)，空间复杂度O(1) 3 class Solution { 4 public: 5 bool search(vector<int>&nums, int target) { 6 int first = 0, last = nums.size()-1; 7 while (first <= last) { 8 const int mid = (first + last) / 2; 9 if (nums[mid] == target) 10 return true; 11 if (nums[first] < nums[mid]) { 12 if (nums[first] <= target && target < nums[mid]) 13 last = mid - 1; 14 else 15 first = mid + 1; 16 } else if (nums[first] > nums[mid]) { 17 if (nums[mid] < target && target <= nums[last]) 18 first = mid + 1; 19 else 20 last = mid; 21 } else 22 //skip duplicate one 23 first++; 24 } 25 return false; 26 } 27 };
LeetCode OJ：Search in Rotated Sorted Array II（翻转排序数组的查找）
原文：http://www.cnblogs.com/-wang-cheng/p/5112433.html