Minimum Number in a Rotated Array

1. Problem Description

Moving some elements from the beginning of an array to the end is called a rotation of the array. Given a rotation of a non-decreasingly sorted array, output the minimum element of the rotated array. For example, {3,4,5,1,2} is a rotation of {1,2,3,4,5}, and its minimum value is 1. NOTE: All given elements are greater than 0. If the array size is 0, return 0.

2. Approach

• Method 1: sequential search, O(N)
• Method 2: binary search. Compared with Find Minimum in Rotated Sorted Array, this problem contains duplicate elements

3. Implementation

3.1. Sequential Search

• java

public class 旋转数组的最小数字
{
    public static void main(String[] args)
    {
        System.out.println(new 旋转数组的最小数字().minNumberInRotateArray(new int[]{3,4,5,1,2}));
        System.out.println(new 旋转数组的最小数字().minNumberInRotateArray(new int[]{5,1,2,3,4}));

    }

    public int minNumberInRotateArray(int[] array)
    {
        // Check parameters
        if (array == null || array.length == 0)
        {
            return 0;
        }
        int min = array[0];
        for (int val : array)
        {
            if (val < min)
            {
                min = val;
            }
        }
        return min;

    }
}

• go

// Brute force
// Time: O(n)
// Space: O(1)
func MinNumberInRotateArray(rotateArray []int) int {
	if len(rotateArray) == 0 {
		return 0
	}

	min := rotateArray[0]
	for _, val := range rotateArray {
		if val < min {
			min = val
		}
	}

	return min
}

3.2. Binary Search

• java

public class 旋转数组的最小数字
{
    public static void main(String[] args)
    {
        System.out.println(new 旋转数组的最小数字().minNumberInRotateArray(new int[]{3, 4, 5, 1, 2}));
        System.out.println(new 旋转数组的最小数字().minNumberInRotateArray(new int[]{5, 1, 2, 3, 4}));
        System.out.println(new 旋转数组的最小数字().minNumberInRotateArray(new int[]{1, 1, 1, 0, 1 }));
    }

    // Binary search
    private int binarySearch(int[] array)
    {
        int left = 0;
        int right = array.length - 1;
        while (left <= right)
        {
            int mid = (left + right) >>> 1;
            // If the middle value is smaller than the right value, the right side is increasing, so the minimum must be on the left: 1,2,3,4,5 -> 5,1,2,3,4
            if (array[mid] < array[right])
            {
                right = mid;
            }
            // With duplicates, the right boundary can only be reduced step by step, so the worst case degrades to O(n)
            else if (array[mid] == array[right])
            {
                right = right - 1;
            }
            // If the middle value is greater than the right value, the rotation break is on the right, so the minimum must be on the right: 1,2,3,4,5 -> 3,4,5,1,2
            else
            {
                left = mid + 1;
            }
        }

        return left;
    }

    public int minNumberInRotateArray(int[] array)
    {
        // Check parameters
        if (array == null || array.length == 0)
        {
            return 0;
        }
        return array[this.binarySearch(array)];

    }
}

• go

// Binary search
// Time: O(log n) on average, O(n) in the worst case
// Space: O(1)
// [3,4,5,1,2]: 5 > 2, so search on the right
// [5,1,2,3,4]: 2 < 4, so search on the left
func MinNumberInRotateArray2(rotateArray []int) int {
	if len(rotateArray) == 0 {
		return 0
	}

	left := 0
	right := len(rotateArray) - 1
	for left < right {
		if rotateArray[left] < rotateArray[right] {
			return rotateArray[left]
		}

		mid := (left + right) >> 1
		// Compare with the right endpoint
		if rotateArray[mid] > rotateArray[right] {
			left = mid + 1
		} else if rotateArray[mid] < rotateArray[right] {
			right = mid
		} else {
			right--
		}
	}

	return rotateArray[left]

}

func minArray(numbers []int) int {
    left := 0
    right := len(numbers) - 1
    for left < right {
        mid := left + (right-left)>>1
        if numbers[mid] > numbers[right] {
            left = mid+1
        }else if numbers[mid] < numbers[right]{
            right = mid
        }else {
            right--
        }
    }
    return numbers[left]
}

4. References

• Minimum Number in a Rotated Array - NowCoder
• Interview Question 11. Minimum Number in a Rotated Array - LeetCode