LeetCode | 81. Search in Rotated Sorted Array II

 

题目：

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).

You are given a target value to search. If found in the array return true, otherwise return false.

Example 1:

Input: nums = [2,5,6,0,0,1,2], target = 0 Output: true

Example 2:

Input: nums = [2,5,6,0,0,1,2], target = 3 Output: false

Follow up:

This is a follow up problem to Search in Rotated Sorted Array, where nums may contain duplicates.Would this affect the run-time complexity? How and why?

 

代码：

class Solution { public: bool search(vector<int>& nums, int target) { int low = 0, high = nums.size() - 1; while(low < high) { int mid = low + (high - low) / 2; if(nums[mid] == target) return true; if(nums[mid] > nums[high]) { if(nums[mid] > target && nums[low] <= target ) high = mid; else low = mid + 1; } else if(nums[mid] < nums[high]) { if(nums[mid] < target && nums[high] >= target) low = mid + 1; else high = mid; } else high--; } if(nums.size() < 1) return false; if(nums[low] == target) return true; return false; } };