leetcode || 81、Search in Rotated Sorted Array II

problem：

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.

Hide Tags   Array Binary Search 題意：對于一個有重複值的已序數組，先将其在某一個位置翻折，再用二分法尋找target是否在該數組中

thinking：

（1）出題人想考察二分法，但是該題的最簡單的算法是周遊查找法，時間複雜度為O（n）

（2）回到二分法，再确定mid的左、右側位置的位置時，考慮到有重複元素的出現，是以每次都要沿着mid往兩遍周遊，時間複雜度最壞也可以達到O（n）

code：

周遊法：

class Solution {
public:
    bool search(int A[], int n, int target) {
        if(NULL == A || 0 == n)
        	return false;
		for(int i = 0; i < n; ++i)
			if(A[i] == target)
				return true;
		return false;
    }
};