【劍指offer】-旋轉數組的最小數字-06/67

一 題目描述

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

輸入一個非遞減排序的數組的一個旋轉，輸出旋轉數組的最小元素。

例如數組{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉，該數組的最小值為1。

NOTE：給出的所有元素都大于0，若數組大小為0，請傳回0。

二 題目分析

1. 該數組原來是一個單調遞增的數組，将前n個數字旋轉到後面，輸出最小的數字，假如數組大小為0的話，則傳回0。
2. 直接周遊循環輸出最小的，這樣的方法是最暴力的（不提倡）
3. 借鑒二分法的思維方式

數組： 3 4 5     1 2 3
      ---1---   ---2---
1. 原數組旋轉後，必然是兩個有序的遞增序列
2. 假如目前中間的元素大于最右面的元素，則證明現在處于2位置 left = mid + 1
3. 假如目前中間的元素小于最右面的元素，則證明現在處于1位置 right = mid
4. 假如目前中間的元素等于最右面的元素，則證明元素中出現了重複的，這時候需要挨個判斷，直接right--
           

三 代碼（Java)

import java.util.ArrayList;
public class Solution {
  public int minNumberInRotateArray(int[] array) {
		int len = array.length;
		if (len == 0) {
			return 0;
		} else {
			int left = 0;
			int right = len - 1;
			while (left < right) {
				int mid = (left + right) / 2;
				if (array[mid] < array[right]) {
					right = mid;
				} else if (array[mid] > array[right]) {
					left = mid + 1;
				}else {
					right--;
				}
			}
			return array[left];
		}
	}
}