剑指offer（Python3）--面试题11：旋转数组的最小值

第2章 面试需要的基础知识

  面试题4：二维数组中的查找

  面试题5：替换空格

  面试题6：从尾到头打印链表

  面试题7：重建二叉树

  面试题9：用两个栈实现队列

  面试题11：旋转数组的最小值

第3章 高质量的代码

第4章 解决面试题的思路

第5章 优化时间和空间效率

第6章 面试中的各项能力

第7章 两个面试案例

---

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

---

解题思路
解法一：
  递归二分法，选取位于中间位置的数进行比较，

1. 中间数大于右边数，返回右边数；
2. 中间数小于左边数，返回左边数；
3. 否则以中间数为分割点，将数组二分，递归进入到两个数组中继续上述比较，若数组长度为1，返回该值。

实战

def minNumberInRotateArray(rotateArray):
	# write code here
	if not rotateArray:
		return 0
	if rotateArray[0] < rotateArray[-1]:
		return rotateArray[0]

	def binary_check(begin, end):
		mid = (begin + end) >> 1
		if begin == end:
			return rotateArray[begin]
		if rotateArray[mid] > rotateArray[mid + 1]:
			return rotateArray[mid + 1]
		if mid > 0 and rotateArray[mid] < rotateArray[mid - 1]:
			return rotateArray[mid]
		left = binary_check(begin, mid)
		right = binary_check(mid + 1, end)
		return min(left, right)

	begin, end = 0, len(rotateArray) - 1
	return binary_check(begin, end)

  上述解法并未完全利用好数组信息，旋转数组中实际上是两个排序数组的组合，上面代码需要分别进入两边数组中查找，显然最小值只存在于一边的数组中，另一半的查找是无用功，这种查找效率不好。
  原因在于上述解法中无法确定最小值在哪一边。对此稍加改进，我们每次比较时用中间值分别和begin，end比较，而不是和mid两边的数比较，这样就可以确定最小值在哪边，直到剩下两个数，这两个数中第二个数即是最小值，而第一个数是最大值。但可能有一种特殊情况，就是A[begin]=A[mid]=A[end]，此种情况下需要顺序遍历剩下数组即可。

class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if not rotateArray:
            return 0
        if rotateArray[0] < rotateArray[-1]:
            return rotateArray[0]

        def traverse(lst):
            minimum = lst[0]
            for num in lst[1:]:
                if num < minimum:
                    minimum = num
            return minimum

        def binary_check(begin, end):
            mid = (begin + end) >> 1
            if begin >= end - 1:
                return rotateArray[end]
            if rotateArray[mid] == rotateArray[begin] == rotateArray[end]:
                return traverse(rotateArray[begin: end+1])
            if rotateArray[mid] >= rotateArray[begin]:
                begin = mid
            if rotateArray[mid] <= rotateArray[end]:
                end = mid
            return binary_check(begin, end)

        return binary_check(0, len(rotateArray) - 1)

解法二：
牛客网
  利用双指针不断二分法缩小查找范围。用中间值和高低位进行比较，看处于递增还是递减序列，进行操作缩小范围。low指向数组开头，high指向数组结尾，mid指向中间位置。

1. 处于递增，即mid大于或等于low，low=mid；

2. 处于递减，即mid小于或等于high，high = mid（如果是high-1，则可能会错过最小值，因为找的就是最小值）

  下面图示和上面解法不同，图中应改地方：
  A[mid] > A[low], low = mid + 1
改为：A[mid] >= A[low], low = mid

  A[mid] < A[high], low = mid
改为：A[mid] <= A[high], low = mid

  其余情况不考虑。当然图中解法也是正确的。

特殊情况处理：
  当A[low]=A[mid]=A[high]时，上述解法无效，因为此时无法判断最小值位于mid的哪一边。
  这时可以遍历查找剩余数组即可。

实战

class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if not rotateArray:
            return 0
        if rotateArray[0] < rotateArray[-1]:
            return rotateArray[0]
        
        def traverse(lst):
            minimum = lst[0]
            for num in lst[1:]:
                if num < minimum:
                    minimum = num
            return minimum
            
        begin, end = 0, len(rotateArray)-1
        while begin + 1 < end:
            mid = (begin + end) >> 1
            if rotateArray[begin] == rotateArray[mid] and rotateArray[mid] == rotateArray[end]:
                return traverse(rotateArray[begin:end+1])
            if rotateArray[mid] >= rotateArray[begin]:
                begin = mid
            if rotateArray[mid] <= rotateArray[end]:
                end = mid
        return rotateArray[end]