旋轉數組的最小數字

題目：把一個數組最開始的若幹個元素搬到數組的末尾，我們稱之為數組的旋轉。輸入一個遞增排序的數組的一個旋轉，輸出旋轉數組的最小元素。例如數組{3，4，5，1，2}為{1，2，3，4，5}的一個旋轉，該數組的最小值為1.

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

我們注意到旋轉之後的數組實際上可以劃分為兩個排序的子數組，而且前面的子數組的元素都大于或者等于後面子數組的元素。我們還可以注意到最小的元素剛好是這兩個子數組的分界線。我們試着用二進制查找法的思路在尋找這個最小的元素。

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

接着我們得到處在數組中間的元素。如果該中間元素位于前面的遞增子數組，那麼它應該大于或者等于第一個指針指向的元素。此時數組中最小的元素應該位于該中間 元素的後面。我們可以把第一指針指向該中間元素，這樣可以縮小尋找的範圍。同樣，如果中間元素位于後面的遞增子數組，那麼它應該小于或者等于第二個指針指 向的元素。此時該數組中最小的元素應該位于該中間元素的前面。我們可以把第二個指針指向該中間元素，這樣同樣可以縮小尋找的範圍。我們接着再用更新之後的 兩個指針，去得到和比較新的中間元素，循環下去。

按 照上述的思路，我們的第一個指針總是指向前面遞增數組的元素，而第二個指針總是指向後面遞增數組的元素。最後第一個指針将指向前面子數組的最後一個元素， 而第二個指針會指向後面子數組的第一個元素。也就是它們最終會指向兩個相鄰的元素，而第二個指針指向的剛好是最小的元素。這就是循環結束的條件。

核心實作代碼：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

<code>int</code> <code>Min(</code><code>int</code> <code>*numbers , </code><code>int</code> <code>length)</code>

<code>{</code>

<code>    </code><code>if</code><code>(numbers == NULL || length &lt;= 0)</code>

<code>        </code><code>return</code><code>;</code>

<code>    </code><code>int</code> <code>index1 = 0;</code>

<code>    </code><code>int</code> <code>index2 = length - 1;</code>

<code>    </code><code>int</code> <code>indexMid = index1;</code>

<code>    </code><code>while</code><code>(numbers[index1] &gt;= numbers[index2])</code>

<code>    </code><code>{</code>

<code>        </code><code>if</code><code>(index2 - index1 == 1)</code>

<code>        </code><code>{</code>

<code>            </code><code>indexMid = index2;</code>

<code>            </code><code>break</code><code>;</code>

<code>        </code><code>}</code>

<code>        </code><code>indexMid = (index1 + index2) / 2;</code>

<code>        </code><code>//如果下标為index1、index2和indexMid指向的三個數字相等，則隻能順序查找</code>

<code>        </code><code>if</code><code>(numbers[index1] == numbers[index2] &amp;&amp; numbers[indexMid] == numbers[index1])</code>

<code>            </code><code>return</code> <code>MinInOrder(numbers , index1 , index2);</code>

<code>        </code><code>if</code><code>(numbers[indexMid] &gt;= numbers[index1])</code>

<code>            </code><code>index1 = indexMid;</code>

<code>        </code><code>else</code> <code>if</code><code>(numbers[indexMid] &lt;= numbers[index2])</code>

<code>            </code><code>index2 = indexMid;</code>

<code>    </code><code>}</code>

<code>    </code><code>return</code> <code>numbers[indexMid];</code>

<code>}</code>

<code>//順序查找</code>

<code>int</code> <code>MinInOrder(</code><code>int</code> <code>*numbers , </code><code>int</code> <code>index1 , </code><code>int</code> <code>index2)</code>

<code>    </code><code>int</code> <code>result = numbers[index1];</code>

<code>    </code><code>for</code><code>(</code><code>int</code> <code>i = index1 + 1 ; i &lt;= index2 ; ++i)</code>

<code>        </code><code>if</code><code>(result &gt; numbers[i])</code>

<code>            </code><code>result = numbers[i];</code>

<code>    </code><code>return</code> <code>result;</code>

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

本題考查了對二分查找的了解。

其中二分查找法的實作代碼如下：

<code>int</code> <code>binary_search(</code><code>int</code> <code>array[] , </code><code>int</code> <code>len , </code><code>int</code> <code>value)</code>

<code>    </code><code>int</code> <code>left = 0;</code>

<code>    </code><code>int</code> <code>right = len - 1;</code>

<code>    </code><code>while</code><code>(left &lt;= right){</code>

<code>        </code><code>int</code> <code>middle = left + ((right - left) &gt;&gt; 1);</code>

<code> </code> 

<code>        </code><code>if</code><code>(array[middle] &gt; value){</code>

<code>            </code><code>right = middle - 1;</code>

<code>        </code><code>else</code> <code>if</code><code>(array[middle] &lt; value){</code>

<code>            </code><code>left = middle + 1;</code>

<code>        </code><code>else</code>

<code>            </code><code>return</code> <code>middle;</code>

<code>         </code> 

<code>    </code><code>return</code> <code>-1;</code>

這是一個經典的話題，如何計算二分查找中的中值？

算法一： mid = (low + high) / 2

算法二： mid = low + (high – low)/2

乍 看起來，算法一簡潔，算法二提取之後，跟算法一沒有什麼差別。但是實際上，差別是存在的。算法一的做法，在極端情況下，(low + high)存在着溢出的風險，進而得到錯誤的mid結果，導緻程式錯誤。而算法二能夠保證計算出來的mid，一定大于low，小于high，不存在溢出的 問題。

本文轉自夏雪冬日部落格園部落格，原文連結：http://www.cnblogs.com/heyonggang/p/3405041.html，如需轉載請自行聯系原作者