【題目描述】
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.
跟進(jìn)“搜索旋轉(zhuǎn)排序數(shù)組”，假如有重復(fù)元素又將如何?是否會(huì)影響運(yùn)行時(shí)間復(fù)雜度？如何影響威鹿？為何會(huì)影響趟济？寫出一個(gè)函數(shù)判斷給定的目標(biāo)值是否出現(xiàn)在數(shù)組中嗅战。
【題目鏈接】
www.lintcode.com/en/problem/search-in-rotated-sorted-array-ii/
【題目解析】
和這題的第一版本類似贯溅，只是可能出現(xiàn)重復(fù)數(shù)字糕篇，而有了重復(fù)數(shù)字會(huì)使問題變得非常復(fù)雜阀蒂。
例如對(duì)于數(shù)組 1 2 2 2 2 2 3该窗，對(duì)第1個(gè)2進(jìn)行翻轉(zhuǎn)后，會(huì)得到2 2 2 2 3 1 2,這個(gè)數(shù)組首尾下標(biāo)為0和6蚤霞，得到中間位置的下標(biāo)為3酗失，于是首尾和中間位置的元素都相同，我們無法判斷索要找的數(shù)字是在前半段還是在后半段昧绣，這種情況下规肴，只能夠從頭開始以O(shè)(n)時(shí)間進(jìn)行一次搜索。
如果不是以上的情況夜畴，還是可以按照第一版本的思路進(jìn)行二分查找拖刃。
【參考答案】
www.jiuzhang.com/solutions/search-in-rotated-sorted-array-ii/
