Android二分查找算法怎么用

本篇內容主要講解“Android二分查找算法怎么用”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“Android二分查找算法怎么用”吧!

旋轉數組的最小數字

題目：把一個數組最開始的若干個元素搬到數組的末尾，我們稱之為數組的旋轉。

輸入一個遞增排序的數組的一個旋轉，輸出旋轉數組的最小元素。例如數組{3，4，5，1，2}為{1，2，3，4，5}的一個旋轉，該數組的最小值為1.

實現數組的旋轉見左旋轉字符串。

解題思路

和二分查找法一樣，用兩個指針分別指向數組的第一個元素和最后一個元素。

我們注意到旋轉之后的數組實際上可以劃分為兩個排序的子數組，而且前面的子數組的元素都大于或者等于后面子數組的元素。

我們還可以注意到最小的元素剛好是這兩個子數組的分界線。我們試著用二元查找法的思路在尋找這個最小的元素。

首先我們用兩個指針，分別指向數組的第一個元素和最后一個元素。按照題目旋轉的規則，第一個元素應該是大于或者等于最后一個元素的（這其實不完全對，還有特例。后面再討論特例）。

接著我們得到處在數組中間的元素。如果該中間元素位于前面的遞增子數組，那么它應該大于或者等于第一個指針指向的元素。

此時數組中最小的元素應該位于該中間 元素的后面。我們可以把第一指針指向該中間元素，這樣可以縮小尋找的范圍。

同樣，如果中間元素位于后面的遞增子數組，那么它應該小于或者等于第二個指針指 向的元素。

此時該數組中最小的元素應該位于該中間元素的前面。我們可以把第二個指針指向該中間元素，這樣同樣可以縮小尋找的范圍。我們接著再用更新之后的 兩個指針，去得到和比較新的中間元素，循環下去。

按照上述的思路，我們的第一個指針總是指向前面遞增數組的元素，而第二個指針總是指向后面遞增數組的元素。

最后第一個指針將指向前面子數組的最后一個元素， 而第二個指針會指向后面子數組的第一個元素。也就是它們最終會指向兩個相鄰的元素，而第二個指針指向的剛好是最小的元素。這就是循環結束的條件。

核心實現代碼：

注意：當兩個指針指向的數字及他們中間的數字三者相同的時候，我們無法判斷中間的數字是位于前面的字數組還是后面的子數組中，也就無法移動兩個指針來縮小查找的范圍。此時，我們不得不采用順序查找的方法。

2 旋轉數組中查找某個數字

要求：一個沒有重復元素的旋轉數組（它對應的原數組是有序的），求給定元素在旋轉數組內的下標（不存在的返回-1）。

例如

有序數組為｛0，1，2，4，5，6，7｝，它的一個旋轉數組為｛4，5，6，7，0，1，2｝。

元素6在旋轉數組內，返回2
元素3不在旋轉數組內，返回-1

分析

遍歷一遍，可以輕松搞定，時間復雜度為O(n)，因為是有序數組旋轉得到，這樣做肯定不是最優解。有序，本能反映用二分查找，舉個例子看看特點
可以看出中間位置兩段起碼有一個是有序的（不是左邊，就是右邊），那么就可以在有序的范圍內使用二分查找；如果不再有序范圍內，就到另一半去找。

參考代碼

擴展

邊的有求是沒有重復的元素，現在稍微擴展下，可以有重復的元素，其他的要求不變。

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

3 數字在排序數組中的出現次數

到此，相信大家對“Android二分查找算法怎么用”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！