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.

看到sorted array就想到binary search，这道题也是binary search的变种，但难点在于array中存在duplicate，需要考虑到会带来新的corner case，反正我是没有想到。。。太弱了。。。一定要弄清楚ascending的判断条件！！！

例子：
若矩阵中没有重复元素，则存在两种情况：
index = 0,1,2,3,4,5,6,7,8,9
array1 = [4,5,6,7,8,9,0,1,2,3]
array2 = [7,8,9,0,1,2,3,4,5,6]

left = 0, right = 9, mid = 4
pivot的位置在右侧时，即0在mid=4右边时，mid=4的左侧递增；
pivot的位置在做左侧时，即0在mid=4左边时，mid=4的右侧递增。

可以根据递增性质判断target是否在左半侧或右半侧，进而选择下一次二分查找的区间。

但当存在重复时，增加一种了新的情况：
index = 0,1,2,3,4,5,6,7,8,9
array1 = [1,1,1,1,1,1,1,1,5,1]
array2 = [1,1,5,1,1,1,1,1,1,1]

此时mid=4时，array[mid]=1，且array[left]=array[right]=1，无法判断哪一侧室递增的。。。

如何解决？
当遇到array[left] = array[mid]时，left++，相对于做一次O(1)的搜索！！！（注意一般情况二分是做了O(lgn)的搜索）。

代码：

bool search(int A[], int n, int key) { 
  int l = 0, r = n - 1; 
  while (l <= r) { 
  int m = l + (r - l)/2; 
  if (A[m] == key) return true; //return m in Search in Rotated Array I 
  if (A[l] < A[m]) { //left half is sorted 
    if (A[l] <= key && key < A[m]) 
      r = m - 1; 
    else 
      l = m + 1; 
  } else if (A[l] > A[m]) { //right half is sorted 
    if (A[m] < key && key <= A[r]) 
      l = m + 1; 
    else 
      r = m - 1; 
  } else 
    l++; 
  } 
  return false;
}

参考
https://discuss.leetcode.com/topic/310/when-there-are-duplicates-the-worst-case-is-o-n-could-we-do-better/3