Search in Rotated Sorted Array II

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.

Analyse: binary search.

Runtime: 10ms.

 1 class Solution {
 2 public:
 3     int findMin(vector<int>& nums) {
 4         if(nums.empty()) return 0;
 5         
 6         int low = 0, high = nums.size() - 1;
 7         while(low < high) {
 8             int mid = low + (high - low) / 2;
 9             
10             if(nums[mid] > nums[high]) low = mid + 1;
11             else if(nums[mid] < nums[high]) high = mid;
12             else high--;
13         }
14         return nums[high];
15     }
16 };

分析：当允许有重复元素出现的时候，那么Search in Rotated Sorted Array中line14：nums[low] <= nums[mid]所能决定的序列就并非单调递增序列，例如[3,1,3,3,3]。在这种情形下，只需将原来的条件拆分为两种情形：

1. nums[low] < nums[mid] 那么之间的序列一定是递增的，代码为Search in Rotated Sorted Array中的line14~17

2. nums[low] == nums[mid] 由于不能够判断数字到底在何处增加、减少，进行low++后观察。因为low++之后nums[low]一定会变大或者保持不变，变大即满足nums[low] > nums[mid]，不变则表示已经进入到重复数字区域。

运行时间 11ms

 1 class Solution {
 2 public:
 3     bool search(vector<int>& nums, int target) {
 4         if(nums.size() == 0) return false;
 5         if(nums.size() == 1){
 6             if(nums[0] == target) return true;
 7             else return false;
 8         }
 9         
10         int low = 0, high = nums.size()-1;
11         while(low <= high){
12             int mid = (low + high) / 2;
13             if(nums[mid] == target) return true;
14             if(nums[low] < nums[mid]){
15                 if(nums[low] <= target && target < nums[mid]) high = mid - 1;
16                 else low = mid + 1;
17             }
18             else if(nums[low] > nums[mid]){
19                 if(nums[mid] < target && target <= nums[high]) low = mid + 1;
20                 else high = mid - 1;
21             }
22             else low++;
23         }
24         return false;
25     }
26 };