Python递归查找旋转排序数组最小元素结果异常求排查

问题定位 #

代码存在3处核心错误导致输出结果不稳定：

• 终止条件逻辑错误：Python列表切片遵循左闭右开规则，data[start:end]的长度不等于当前有效区间的元素个数，原逻辑会导致终止条件判断提前或延后失效。
• 区间归属判断逻辑错误：原判断最小值所在区间的条件不符合旋转排序数组的特性，正确逻辑应该是对比中间值和右边界值：如果中间值大于右边界值，说明最小值在右半区间；否则最小值在左半区间。
• mid参数传递冗余：mid不需要从外层传入，每次递归时根据当前start和end计算即可，避免传参失误。

修正后的纯递归实现代码 #

def getMin(data, start, end):
    # 区间仅剩一个元素，直接返回
    if start == end:
        return data[start]
    # 区间仅剩两个元素，返回较小值
    if end - start == 1:
        return min(data[start], data[end])
    # 计算当前区间中点
    mid = (start + end) // 2
    # 中间值大于右边界，最小值在右半区间
    if data[mid] > data[end]:
        return getMin(data, mid + 1, end)
    # 否则最小值在左半区间
    else:
        return getMin(data, start, mid)

def FindMin(data):
    # 空数组兼容
    if not data:
        return None
    return getMin(data, 0, len(data) - 1)


# 以下是原有测试代码，无需修改
import random as rd
numOfElem = 10

data =  sorted(rd.sample(range(1,40), numOfElem))
print ("ONLY Sorted Data is        == ", data)

# get random number to move element by that number
movebysize= rd.randint(1,10)
print ("Move Sorted data by size   == ", movebysize)

# Make array rotated
data = data[movebysize:] + data[:movebysize]
print ("Data Sorted and Rotated is == ", data)

# Find Min:
print (" Min is ==== ", FindMin(data))

内容的提问来源于stack exchange，提问作者Vipin