算法题：有序数组旋转之后，找出其最小值

逃离我推掉我的手 2022-12-29 02:09 197阅读 0赞

### 有序数组旋转之后，找出其最小值 ###

*  题目描述
 *  代码
 *  执行过程

# 题目描述 #

给定一个非空整数有序数组，向左旋转K次，k未知，用最高效的方法找出旋转之后数组的最小值

这是我面试BAT其中某家广告算法工程师时的面试题，面试官给我题的时候，因为面试岗位是算法工程师，首先应该考虑的是时间复杂度和空间复杂度，且是有序数组，我首先想到的是二分查找，时间复杂度为O(logn)。

# 代码 #

import pysnooper
    list1 = [6,7,8,9,10,2,3,4,5]
    ''' 这个数组的形状长这样 10 9 8 7 6 5 4 3 2 按照大小画出图，应该是两段线，第一个元素大于最后一个元素 用二分查找，查找一次，扔掉一半数组，将数组长度变为原来的一半，时间复杂度为O(logn) 那么什么时候就找到了呢？ 也就是第一个元素小于最后一个元素，此时这个小数组是有序的，也找到了最小值 '''
    #@pysnooper.snoop()#pysnooper是装饰器，可以修改函数，作用是打印函数的参数
    def fun1(list1):
        low = 0
        hi = len(list1) - 1
        while list1[low] > list1[hi] and (hi-low)!=1:
            m = int((low+hi)/2)
            if list1[m] > list1[hi]:
                low = m
            else:
                hi = m
        return min(list1[low],list1[hi])
    print(fun1(list1))

# 执行过程 #

Starting var:.. list1 = [6, 7, 8, 9, 10, 2, 3, 4, 5]
    12:08:36.195916 call        21 def fun1(list1):
    12:08:36.196918 line        22     low = 0
    New var:....... low = 0
    12:08:36.196918 line        23     hi = len(list1) - 1
    New var:....... hi = 8
    12:08:36.196918 line        24     while list1[low] > list1[hi] and (hi-low)!=1:
    12:08:36.196918 line        25         m = int((low+hi)/2)
    New var:....... m = 4
    12:08:36.196918 line        26         if list1[m] > list1[hi]:
    12:08:36.196918 line        27             low = m
    Modified var:.. low = 4
    12:08:36.196918 line        24     while list1[low] > list1[hi] and (hi-low)!=1:
    12:08:36.196918 line        25         m = int((low+hi)/2)
    Modified var:.. m = 6
    12:08:36.196918 line        26         if list1[m] > list1[hi]:
    12:08:36.196918 line        29             hi = m
    Modified var:.. hi = 6
    12:08:36.196918 line        24     while list1[low] > list1[hi] and (hi-low)!=1:
    12:08:36.196918 line        25         m = int((low+hi)/2)
    Modified var:.. m = 5
    12:08:36.196918 line        26         if list1[m] > list1[hi]:
    12:08:36.196918 line        29             hi = m
    Modified var:.. hi = 5
    12:08:36.196918 line        24     while list1[low] > list1[hi] and (hi-low)!=1:
    12:08:36.196918 line        30     return min(list1[low],list1[hi])
    12:08:36.196918 return      30     return min(list1[low],list1[hi])
    Return value:.. 2