Android二分查找算法怎么用

本篇內(nèi)容主要講解“Android二分查找算法怎么用”，感興趣的朋友不妨來看看。本文介紹的方法操作簡(jiǎn)單快捷，實(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è)元素和最后一個(gè)元素。

我們注意到旋轉(zhuǎn)之后的數(shù)組實(shí)際上可以劃分為兩個(gè)排序的子數(shù)組，而且前面的子數(shù)組的元素都大于或者等于后面子數(shù)組的元素。

我們還可以注意到最小的元素剛好是這兩個(gè)子數(shù)組的分界線。我們?cè)囍枚檎曳ǖ乃悸吩趯ふ疫@個(gè)最小的元素。

首先我們用兩個(gè)指針，分別指向數(shù)組的第一個(gè)元素和最后一個(gè)元素。按照題目旋轉(zhuǎn)的規(guī)則，第一個(gè)元素應(yīng)該是大于或者等于最后一個(gè)元素的（這其實(shí)不完全對(duì)，還有特例。后面再討論特例）。

接著我們得到處在數(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è)指針會(huì)指向后面子數(shù)組的第一個(gè)元素。也就是它們最終會(huì)指向兩個(gè)相鄰的元素，而第二個(gè)指針指向的剛好是最小的元素。這就是循環(huán)結(jié)束的條件。

核心實(shí)現(xiàn)代碼：

注意：當(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ù)組（它對(duì)應(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)，就到另一半去找。

參考代碼

擴(kuò)展

邊的有求是沒有重復(fù)的元素，現(xiàn)在稍微擴(kuò)展下，可以有重復(fù)的元素，其他的要求不變。

思路：大致思路與原來相同，這是需要比較A[beg] 與　A[mid]的關(guān)系

3 數(shù)字在排序數(shù)組中的出現(xiàn)次數(shù)

到此，相信大家對(duì)“Android二分查找算法怎么用”有了更深的了解，不妨來實(shí)際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！