LeetCode Q81: 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.

	class Solution {
	public:
	bool search(vector<int>& nums, int target) {
	int left=0, right=nums.size()-1;
	while(left<=right){
	int mid=(left+right)/2;
	if(target==nums[mid])
	return true;
	if(nums[mid]>nums[right]){
	if(target < nums[mid] && target >= nums[left])
	right=mid-1;
	else
	left=mid+1;
	}else if(nums[mid] < nums[right]){
	if(target > nums[mid] && target<=nums[right])
	left=mid+1;
	else
	right=mid-1;
	}else if(nums[mid] == nums[right])
	// This is the only difference to the problem of Search in Rotated Array I.
	// With duplicate elements in the array. The problem happens only when the same
	// elements are showing in the same time at left, mid and right. For example:
	// [1, 3, 1, 1, 1] and we look for [3].
	// The idea is to shrink the array to remove duplicate elements on the right of mid.
	right--;
	}
	return false;
	}
	};

view raw Q81SearchSortedArrayII.cpp hosted with ❤ by GitHub