旋转数组的最小数字

题目描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

package SwordOffer;

/** * @author jinhuajian * @data 2018年12月28日---下午2:18:10 * @blog https://me.csdn.net/qq_37119939 */
public class Solution_06 {

	// 跟左边的比，比不出来，脑子要活，mid跟右边界比
	public int minNumberInRotateArray_1(int[] array) {
		if (array == null || array.length < 1)
			return 0;
		int l = 0, r = array.length - 1;
		while (l < r) {
			int mid = l + (r - l) / 2;
			if (array[mid] > array[r]) {// 最小值肯定在mid的右边
				l = mid + 1;
			} else if (array[mid] < array[r]) {// 最小值肯定mid的左边或者就是mid;{4,5,1,2,3} array[mid]=1<array[r]=3
				r = mid;
			} else {// 出现这种情况的array类似 [1,0,1,1,1] 或者[1,1,1,0,1]，此时最小数字不好判断在mid左边
				// 还是右边,这时只好一个一个试 ，
				r = r - 1;
			}
		}
		return array[l];
	}

	// {1,2,3,4,5,6,7}, {5,6,7,1,2,3,4}
	public static void main(String[] args) {
		Solution_06 s = new Solution_06();
		int[] arr = { 3, 4, 5, 1, 2 };
		int res = s.minNumberInRotateArray_1(arr);
		System.out.println(res);
	}
}

Python版

class Solution:
    def minNumberInRotateArray(self, arr):
        # write code here
        m = len(arr)
        if m == 0:
            return
        if m == 1:
            return arr[0]
        mid =l = 0
        r = m - 1

        while arr[l] >= arr[r]:
            if l == r-1:
                mid = r
                break
            #如果arr[0] = arr[r] = arr[mid],只能用从头到尾顺序查找顺序查找
            if arr [0] == arr[r] and arr[r] == arr[mid]:
                while l < r -1:
                    if arr[l] >= arr[0]:
                        l += 1
                    else:break
                return arr[l]

            mid = (l + r) // 2
            #if arr[mid] > arr[0]:
            if arr[mid] >= arr[l]:
                l = mid
            elif arr[mid] <= arr[r]:
                r = mid

        return arr[mid]