【移動(dòng)應(yīng)用開發(fā)技術(shù)】Android二分查找算法怎么用

【移動(dòng)應(yīng)用開發(fā)技術(shù)】Android二分查找算法怎么用

本篇內(nèi)容主要講解“Android二分查找算法怎么用”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實(shí)用性強(qiáng)。下面就讓在下來帶大家學(xué)習(xí)“Android二分查找算法怎么用”吧!旋轉(zhuǎn)數(shù)組的最小數(shù)字題目：把一個(gè)數(shù)組最開始的若干個(gè)元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)。輸入一個(gè)遞增排序的數(shù)組的一個(gè)旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。例如數(shù)組{3，4，5，1，2}為{1，2，3，4，5}的一個(gè)旋轉(zhuǎn)，該數(shù)組的最小值為1.實(shí)現(xiàn)數(shù)組的旋轉(zhuǎn)見左旋轉(zhuǎn)字符串。題目：把一個(gè)數(shù)組最開始的若干個(gè)元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)。輸入一個(gè)遞增排序的數(shù)組的一個(gè)旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。例如數(shù)組{3，4，5，1，2}為{1，2，3，4，5}的一個(gè)旋轉(zhuǎn)，該數(shù)組的最小值為1.實(shí)現(xiàn)數(shù)組的旋轉(zhuǎn)見左旋轉(zhuǎn)字符串。解題思路和二分查找法一樣，用兩個(gè)指針分別指向數(shù)組的第一個(gè)元素和最后一個(gè)元素。我們注意到旋轉(zhuǎn)之后的數(shù)組實(shí)際上可以劃分為兩個(gè)排序的子數(shù)組，而且前面的子數(shù)組的元素都大于或者等于后面子數(shù)組的元素。我們還可以注意到最小的元素剛好是這兩個(gè)子數(shù)組的分界線。我們試著用二元查找法的思路在尋找這個(gè)最小的元素。首先我們用兩個(gè)指針，分別指向數(shù)組的第一個(gè)元素和最后一個(gè)元素。按照題目旋轉(zhuǎn)的規(guī)則，第一個(gè)元素應(yīng)該是大于或者等于最后一個(gè)元素的（這其實(shí)不完全對，還有特例。后面再討論特例）。接著我們得到處在數(shù)組中間的元素。如果該中間元素位于前面的遞增子數(shù)組，那么它應(yīng)該大于或者等于第一個(gè)指針指向的元素。此時(shí)數(shù)組中最小的元素應(yīng)該位于該中間元素的后面。我們可以把第一指針指向該中間元素，這樣可以縮小尋找的范圍。同樣，如果中間元素位于后面的遞增子數(shù)組，那么它應(yīng)該小于或者等于第二個(gè)指針指向的元素。此時(shí)該數(shù)組中最小的元素應(yīng)該位于該中間元素的前面。我們可以把第二個(gè)指針指向該中間元素，這樣同樣可以縮小尋找的范圍。我們接著再用更新之后的兩個(gè)指針，去得到和比較新的中間元素，循環(huán)下去。按照上述的思路，我們的第一個(gè)指針總是指向前面遞增數(shù)組的元素，而第二個(gè)指針總是指向后面遞增數(shù)組的元素。最后第一個(gè)指針將指向前面子數(shù)組的最后一個(gè)元素，而第二個(gè)指針會指向后面子數(shù)組的第一個(gè)元素。也就是它們最終會指向兩個(gè)相鄰的元素，而第二個(gè)指針指向的剛好是最小的元素。這就是循環(huán)結(jié)束的條件。核心實(shí)現(xiàn)代碼：https://upload-images.jianshu.io/upload_images/3117364-28a99958ebdd7ad1?imageMogr2/auto-orient/strip注意：當(dāng)兩個(gè)指針指向的數(shù)字及他們中間的數(shù)字三者相同的時(shí)候，我們無法判斷中間的數(shù)字是位于前面的字?jǐn)?shù)組還是后面的子數(shù)組中，也就無法移動(dòng)兩個(gè)指針來縮小查找的范圍。此時(shí)，我們不得不采用順序查找的方法。2旋轉(zhuǎn)數(shù)組中查找某個(gè)數(shù)字要求：一個(gè)沒有重復(fù)元素的旋轉(zhuǎn)數(shù)組（它對應(yīng)的原數(shù)組是有序的），求給定元素在旋轉(zhuǎn)數(shù)組內(nèi)的下標(biāo)（不存在的返回-1）。例如有序數(shù)組為｛0，1，2，4，5，6，7｝，它的一個(gè)旋轉(zhuǎn)數(shù)組為｛4，5，6，7，0，1，2｝。元素6在旋轉(zhuǎn)數(shù)組內(nèi)，返回2元素3不在旋轉(zhuǎn)數(shù)組內(nèi)，返回-1分析遍歷一遍，可以輕松搞定，時(shí)間復(fù)雜度為O(n)，因?yàn)槭怯行驍?shù)組旋轉(zhuǎn)得到，這樣做肯定不是最優(yōu)解。有序，本能反映用二分查找，舉個(gè)例子看看特點(diǎn)可以看出中間位置兩段起碼有一個(gè)是有序的（不是左邊，就是右邊），那么就可以在有序的范圍內(nèi)使用二分查找；如果不再有序范圍內(nèi)，就到另一半去找。參考代碼https://upload-images.jianshu.io/upload_images/3117364-5467a6bd9478bb9b?imageMogr2/auto-orient/strip擴(kuò)展邊的有求是沒有重復(fù)的元素，現(xiàn)在稍微擴(kuò)展下，可以有重復(fù)的元素，其他的要求不變。思路：大致思路與原來相同，這是需要比較A[beg]與A[mid]的關(guān)系https://upload-images.jianshu.io/upload_images/3117364-10408ab72f414310?imageMogr2/auto-orient/strip3數(shù)字在排序數(shù)組中的出現(xiàn)次數(shù)https://upload-images.jianshu.io/upload_images/3117364-651877eab930784f?imageMogr2/auto-orient/stripht