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的變種，但難點(diǎn)在于array中存在duplicate残制，需要考慮到會(huì)帶來(lái)新的corner case梦染，反正我是沒(méi)有想到忿檩。东抹。。太弱了本缠。斥扛。。一定要弄清楚ascending的判斷條件５で隆Ｏ“洹！
例子：
若矩陣中沒(méi)有重復(fù)元素楣黍，則存在兩種情況：
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的位置在右側(cè)時(shí)匾灶，即0在mid=4右邊時(shí)，mid=4的左側(cè)遞增租漂；
pivot的位置在做左側(cè)時(shí)阶女，即0在mid=4左邊時(shí)，mid=4的右側(cè)遞增哩治。
可以根據(jù)遞增性質(zhì)判斷target是否在左半側(cè)或右半側(cè)秃踩，進(jìn)而選擇下一次二分查找的區(qū)間。
但當(dāng)存在重復(fù)時(shí)业筏，增加一種了新的情況：
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]
此時(shí)mid=4時(shí)憔杨，array[mid]=1，且array[left]=array[right]=1蒜胖，無(wú)法判斷哪一側(cè)室遞增的消别。。翠勉。
如何解決妖啥？
當(dāng)遇到array[left] = array[mid]時(shí)，left++对碌，相對(duì)于做一次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;
}
