LeetCode 81 Search in Rotated Sorted Array II

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的判斷條件5で隆O“洹!

例子:
若矩陣中沒(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)的搜索>J!!(注意一般情況二分是做了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

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末诉位,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子菜枷,更是在濱河造成了極大的恐慌苍糠,老刑警劉巖,帶你破解...
    沈念sama閱讀 223,126評(píng)論 6 520
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件啤誊,死亡現(xiàn)場(chǎng)離奇詭異岳瞭,居然都是意外死亡,警方通過(guò)查閱死者的電腦和手機(jī)蚊锹,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,421評(píng)論 3 400
  • 文/潘曉璐 我一進(jìn)店門(mén)瞳筏,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái),“玉大人牡昆,你說(shuō)我怎么就攤上這事姚炕。” “怎么了丢烘?”我有些...
    開(kāi)封第一講書(shū)人閱讀 169,941評(píng)論 0 366
  • 文/不壞的土叔 我叫張陵柱宦,是天一觀的道長(zhǎng)。 經(jīng)常有香客問(wèn)我播瞳,道長(zhǎng)掸刊,這世上最難降的妖魔是什么? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 60,294評(píng)論 1 300
  • 正文 為了忘掉前任狐史,我火速辦了婚禮痒给,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘骏全。我一直安慰自己,他們只是感情好尼斧,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,295評(píng)論 6 398
  • 文/花漫 我一把揭開(kāi)白布姜贡。 她就那樣靜靜地躺著,像睡著了一般棺棵。 火紅的嫁衣襯著肌膚如雪楼咳。 梳的紋絲不亂的頭發(fā)上,一...
    開(kāi)封第一講書(shū)人閱讀 52,874評(píng)論 1 314
  • 那天烛恤,我揣著相機(jī)與錄音母怜,去河邊找鬼。 笑死缚柏,一個(gè)胖子當(dāng)著我的面吹牛苹熏,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播,決...
    沈念sama閱讀 41,285評(píng)論 3 424
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼轨域,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼袱耽!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起干发,我...
    開(kāi)封第一講書(shū)人閱讀 40,249評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤朱巨,失蹤者是張志新(化名)和其女友劉穎,沒(méi)想到半個(gè)月后枉长,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體冀续,經(jīng)...
    沈念sama閱讀 46,760評(píng)論 1 321
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,840評(píng)論 3 343
  • 正文 我和宋清朗相戀三年必峰,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了洪唐。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,973評(píng)論 1 354
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡自点,死狀恐怖桐罕,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情桂敛,我是刑警寧澤功炮,帶...
    沈念sama閱讀 36,631評(píng)論 5 351
  • 正文 年R本政府宣布,位于F島的核電站术唬,受9級(jí)特大地震影響薪伏,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜粗仓,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,315評(píng)論 3 336
  • 文/蒙蒙 一嫁怀、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧借浊,春花似錦塘淑、人聲如沸。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 32,797評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至曙蒸,卻和暖如春捌治,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背纽窟。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 33,926評(píng)論 1 275
  • 我被黑心中介騙來(lái)泰國(guó)打工肖油, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人臂港。 一個(gè)月前我還...
    沈念sama閱讀 49,431評(píng)論 3 379
  • 正文 我出身青樓森枪,卻偏偏與公主長(zhǎng)得像视搏,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子疲恢,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,982評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容