LeetCode Search in Rotated Sorted Array II

Search in Rotated Sorted Array II

Follow up for "Search in Rotated Sorted Array":
What if duplicates are>[1,3,1,1,1], 3

Would this affect the run-time complexity How and why --run-time的最坏情况是O(n)了，因为特殊情况出现的时候需要额外处理，可能做线性搜索

Write a function to determine if a given target is in the array.

//本题重点考查特殊情况：
//[1,3,1,1,1], 3
class Solution {
public:
	bool search(int A[], int n, int target) 
	{
		return biSearch(A, 0, n-1, target);
	}

	bool biSearch(int A[], int low, int up, int tar)
	{
		if (low > up) return false;

		int mid = low + ((up-low)>>1);
		if (A[mid] == tar) return true;

		if (A[low] < A[mid])
		{
			if (A[low] <= tar && tar < A[mid]) return biSearch(A, low, mid-1, tar);
			else return biSearch(A, mid+1, up, tar);

		}
		else if (A[low] > A[mid])
		{
			if (A[mid]