有效的java，Find Minimum in Rotated Sorted Array leetcode java

?題目：

有效的java。Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

java in，You may assume no duplicate exists in the array.

?

解題思路：

java instanceof，首先假設一個sorted沒有rotated的數組[1,2,3]，假設我們通過一個pivot把這個數組rotate，那么結果可能為：[2,3,1], [3,1,2], 可以發現：num[low]永遠大于（或等于）num[high]。因為你之前是sorted的數組，你在一個sorted的數組找了一個pivot進行rotate，那么比如pivot后面的值都大于pivot之前的值。所以依據這個發現，以及二分法查找。我們可以根據以下判斷來解題。num[mid]有兩種可能性，如果num[mid] > num[high]，證明num[mid]在rotated后的那個區間內，這個區間我們剛才已知都大于pivot之前的值，所以最小值就在low=mid+1那個區間內。另一種可能，num[mid] <= num[high]，那么我們剛才可以看出來這種可能性說明mid~high以及是排好序的，那么最小值在high=mid這個區間內（mid可能是最小值）。依據此判斷可以找到最小值。

?

?

java search.addfilteror、?

代碼如下：

?1?????public?int?findMin(int[]?num)?{
?2?????????int?low?=?0,?high?=?num.length?-?1;
?3?????????while?(low?<?high?&&?num[low]?>=?num[high])?{
?4?????????????int?mid?=?(low?+?high)?/?2;
?5?????????????if?(num[mid]?>?num[high])
?6?????????????????low?=?mid?+?1;
?7?????????????else
?8?????????????????high?=?mid;
?9?????????}
10?????????return?num[low];
11?????}

?