练习1：在旋转有序数列中查找最小值

题目要求

假设有一个升序排列的数列在某个未知节点处被前后调换，请找到数列中的最小值。

分析

旋转有序数列是数据的先验结构，对于这个结构特性，设计针对性的搜索算法。

代码1——我的

def f(num_list):
    if len(num_list) == 0:
        return -1

    l, h = 0, len(num_list)-1
    while l+1 < h:
        mid = (l+h) // 2
        if num_list[mid] >= num_list[l]:
            l = mid
        else:
            h = mid

    if num_list[l] >= num_list[h]:
        return num_list[h]
    else:
        return num_list[l]

代码2——官方的

def search(alist):
    if len(alist) == 0:
        return -1

    l, r = 0, len(alist)-1
    while l+1 < h:
        if alist[l] < alist[r]:
            return alist[l]
        mid = l + (r - l) //2
        if alist[mid] >= alist[l]:
            l = mid +1
        else:
            r = mid
    return alist[l] if alist[l] < alist[r] else alist[r]

代码对比

1. 官方代码中循环内部多了if alist[l] <alist[r]: return alist[l]，以捕获运气好的情况，以直接得到答案
2. 用l + (r - l) //2代替(l + r) // 2，这样可以预防数值过大所导致的溢出
3. 最后的return比较简洁，一行