旋转数组的最小数字

题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为 1。

image.png

在数组{3, 4, 5, 1, 2}中查找最小值的过程：

旋转数组中包含两个递增排序的子数组，有阴影的是第二个子数组。

1. 把P₁指向数组的第一个数字，P₂指向数组的最后一个数字。由于P₁和P₂中间的数字5大于P₁指向的数字，中间的数字在第一个子数组中。下一步把P₁指向中间的数字。

2. P₁和P₂中间的数字1小于P₂指向的数字，中间的数字放在第二个子数组中。下一步把P₂指向中问的数字。

3. P₁和P₂指向两个相邻的数字，则P₂指向的是数组中的最小数字。

---

前面我们提到，在旋转数组中，由于是把递增排序数组前面的若干个数字搬到数组的后面，因此第一个数字总是大于或者等于最后一个数字。

如果把排序数组的前面的0个元素搬到最后面，即排序数组本身，这仍然是数组的一个旋转。此时，数组中的第一个数字就是最小的数字，可以直接返回。即：一旦发现数组中第一个数字小于最后一个数字，表明该数组是排序的，就可以直接返回第一个数字。

假如数组类似于{0, 1, 1, 1, 1}或{1, 1, 1, 0, 1}。在这两种情况中，第一个指针和第二个措针指向的数字都是 1，并且两个指针中间的数字也是1，这3个数字相同。在第一种情况中，中间数字（下标为2）位于后面的子数组；在第二种情況中，中间数字（下标为2）位于前面的子数组。因此，当两个指针指向的数字及它们中间的数宇三者相同的时候，我们无法判断中间的数字是位于前面的子数组还是后面的子数组，也就无法移动两个指针来缩小查找的范围。此时，我们不得不采用顺序查找的方法。

func min(_ numbers: [Int]) -> Int? {
    guard !numbers.isEmpty else { return nil }
    if numbers.count == 1 {
        return numbers.first
    }
    
    var index1: Int = 0
    var index2: Int = numbers.count - 1
    var indexMid = index1
    
    while numbers[index1] >= numbers[index2] {
        if index2 - index1 == 1 {
            indexMid = index2
            break
        }
        
        indexMid = (index1 + index2) / 2
        
        // 如果下标为index1、index2、indexMid指向的三个数字相等，则只能顺序查找
        if numbers[index1] == numbers[index2] && numbers[indexMid] == numbers[index1] {
            return minInOrder(numbers, index1, index2)
        }
        
        if numbers[indexMid] >= numbers[index1] {
            index1 = indexMid
        } else if (numbers[indexMid] <= numbers[index2]) {
            index2 = indexMid
        }
    }
    
    return numbers[indexMid]
}

func minInOrder(_ numbers: [Int], _ index1: Int, _ index2: Int) -> Int {
    var result = numbers[index1]
    for i in (index1 + 1)...index2 {
        if result > numbers[i] {
            result = numbers[i]
        }
    }
    
    return result
}

摘抄资料：《剑指offer》