leetcode 81: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.

思路：

思路和leetcode 33:Revised Binary Search類似，隻不過需要考慮重複的情況。

比如：

11111311111111111

如果照以前的方法，low,mid,high都是1，不知那邊是排好序的哪邊是沒有排好序的。

但是這樣情況下，[low,mid]與[mid,high]兩者之間必有一個是全為1的，是以需要一個judge函數來判斷哪邊全為1.

實作如下：

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

下面提供一種更為簡潔的方法，思路和上面類似，隻不過對nums[mid]=nums[high]的處理更為巧妙。

時間複雜度：O（lgn）

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