Find the minimum value in a rotated sorted array.

The core idea of solving the problem is: binary search. Then, distinguish the different situations after rotation to make specific adjustments.

The first questionFind the minimum value in the rotation sort array

The key point of this problem is

  • Ascending order
  • Different elements
  • Return the smallest element

In the code, I still consider the case of repeating elements. First, considering repeating elements does not impose an additional burden on code execution because the input elements are different. Second, consider repeating elements, which unites this problem with the next one.

Please refer to the comments for details. The reader should think more about the examples in the notes and exclude some sections by contradiction.

To sum up. There are four possibilities for analyzing an interval:

  • The left element of the interval is less than the right element
  • The left element of the interval is larger than the middle element
  • The middle element is larger than the right element
  • The left, middle, and right elements of the interval are equal

Take full advantage of what we know, narrow the search area as much as possible.

The solution is as follows (code submission passes).

func findMin(nums []int) int {
    l := len(nums)
    if l == 0 {
        panic("nums is empty")}var (
        low int
        high = l- 1
    )
OuterLoop:
    for low <= high {
        // If the left element of the current interval is smaller than the right element,
        // Then the area is ordered from small to large,
        / / as /..., 1, 2, 3, 4, 5,... , 1 < 5.
        if nums[low] < nums[high] {
            // The minimum is the left element.
            return nums[low]
        }
        
        // Middle position
        mid := low + (high-low)>>1
        v := nums[mid]
        
        // If the left element of the current interval is larger than the middle element,
        / / such as [... and 6,7,1,2,3,4,5...]. , 6 > 2.
        // Then the minimum value is in the index interval [low+1,mid].
        // Why does the minimum value not appear in the index interval (mid,high)?
        // If the minimum value appears in the index range (mid,high),
        [...,6,7,1,2,3,-1,5]
        // It is not ordered before rotation,
        // So the minimum value does not appear in the index interval (mid,high).
        if nums[low] > v {
            // nums[low] is larger than an element, which is definitely not the smallest element, so it is not included.
            low++
            // nums[mid] is the smallest element to include.
            high = mid
            continue
        }
        
        // If the middle element of the current interval is larger than the right element,
        / / such as [... and 4,5,6,7,1,2,3...]. , 7 > 3.
        // Then the smallest element is in the index interval (mid,high).
        // Why does the minimum value not appear in the index interval [low,mid],
        // According to the previous explanation, the same argument can be proved.
        if v > nums[high] {
            // nums[mid] is greater than an element.
            low = mid+1
            // nums[high] is a small, possibly minimum value, so high does not change.
            continue
        }
        
        Nums [mid] == nums[high]
        Nums [mid] <= nums[high]
        // If there is a case of less than, it must be dealt with at the beginning of the loop,
        Nums [low] < nums[high]
        // Walk through the area, making the most of the available conditions.
        for i := low; i < high; i++ {
            // A smaller value is found, which is the minimum value.
            / / such as [... and 9,9,1,2,9,9,9,9,9...].
            / / or [... and 9,9,9,9,9,9,1,2,9...].
            if nums[i] > nums[i+1] {
                return nums[i+1]}// A large value is found.
            / / as /..., 2,3,6,1,2,2,2,2,2,...
            / / or /..., 2,2,2,2,2,3,6,1,2,...
            if nums[i] < nums[i+1] {
                if i+2 == mid {
                    / / as /..., 2,2,2,5,2,2,2,2,2,...
                    return v
                }
                // nums[I +1] is definitely not the minimum, so I +2 is the new low.
                / / as /..., 2,5,0,1,2,2,2,2,2,... , I +2 < mid.
                / / as /..., 2,2,2,2,2,5,0,1,2,... , I +2 > mid.
                low = i+2
                if i+2 < mid {
                    // index (mid,high) cannot be lower than nums[mid].
                    // So the minimum value is in the index interval [I +2,mid].
                    // nums[mid] may be the minimum value to include.
                    high = mid
                }
                // Note: jump to the outer for loop
                continue OuterLoop
            }
        }
        // All equal, each is the minimum
        break
    }
    return nums[low]
}
Copy the code

The second questionFind the minimum value II in the rotation sort array

The key point of this problem is

  • Ascending order
  • There are duplicate elements
  • Return the smallest element

This problem can be solved directly using the code in the previous problem, because the code in the previous problem already takes into account repeating elements.

The third questionRotate the smallest number in the array

This is the same problem as the last one.