python实现找出旋转数组的最小元素

题目描述:
把一个有序数组最开始的若干个元素搬到数组的末尾，称之为数组的旋转 。输入一个排
好序的数组的 一个旋转，输出旋转数组的最小元素 。 例如数组[3, 4, 5, 1, 2]为数组[1, 2, 3, 4, 5] 的一个旋转，该数组的最小值为 1。
对于本题的解决方案，最容易想到的，也是最简单的方法就是直接遍历法。但是这种方 法显然没有用到题目中旋转数组的特性，因此，它的效率比较低下，下面介绍 一种比较高效 的 二 分查找法。
通过数组的特性可以发现，数组元素首先是递增的，然后 突然 下降到 最 小值，然 后再递 增。虽然如此，但是还有下面三种特殊情况需要注意 :
(1)数组本身 是没有发生过旋转的，是一个有序的数组，例如序列[ 1,2,3,4,5,6]。
(2) 数组中元素值全部相等，例如序列 [1,l,l,1,1,1]。
(3)数组中元素值大部分都相等 ，例如序列[1,0,l,l,1,1]。 通过旋转数组的定义可知，经过旋转之后的数组实际上可以划分为两个有序的子数组，
前面的子数组的元素值都大于或者等于后面子数组的元素值 。可以根据数组元素的这个特点， 采用二分查找的思想不断缩小查找范围 ， 最终找 出问题的解决方案 ， 具体实现思路如下所示: 按照二分查找的思想，给定数组 a汀， 首先定义两个变量 low和 high，分别表示数组的第
一个元素和最后一个元素的下标。 按照题目中对旋转规则的定义，第一个元素应该是大于或 者等于最后一个元素的(当旋转个数为 0，即没有旋转的时·候，要单独处理，直接返回数组第 一个元素) 。接着遍历数组中 间的元素 arr[mid]， 其中 mid=(high+low)/2
(1)如果 arr[mid] <arr[mid一 1]，则相arr[mid]一定是最小值;
(2)如果 arr[mid+ l] <arr[mid]，则 arr[mid+ l]一定是最小值;
(3)如果 arr[high]>arr[mid]，贝lj最小值一定在数组左半部分:
(4) 如果 aη[mid]>aη[low]，则最小值一定在数组右半部分;
(5)如果 arr[low] = arr[mid] 且 即[high]==[mid]，则此时无法区分最小值是在数组 的左半部分还是右半部分( 例如:[2,2,2,2,1,2], [2,1,2,2,2,2])。 在这种情况下，只能分别在 数组的左右两部分找最小值 minL与 minR，最后求出 minL与 minR的最小值。

def getMin_1(arr,low,high):
    if high<low:
        return arr[0]
    if high==low:
        return arr[low]
    mid=(high-low)//2
    if arr[mid]<arr[mid-1]:
        return arr[mid]
    elif arr[mid+1]<arr[mid]:
        return arr[mid+1]
    elif arr[high]>arr[mid]:
        return getMin(arr,low,mid-1)
    elif arr[mid]>arr[low]:
        return getMin(arr,mid+1,high)
    else:
        return min(getMin(arr,low,mid-1),getMin(arr,mid+1,high))
def getMin(arr):
    if arr==None:
        print('参数不合法')
        return
    else:
        return getMin_1(arr,0,len(arr)-1)
if __name__=='__main__':
    array1=[5,6,1,2,3,4]
    mins=getMin(array1)
    print(mins)
    array2=[1,1,0,1]
    mins=getMin(array2)
    print(mins)

输出：
1
0

本文地址：https://blog.csdn.net/weixin_42813521/article/details/107654765