01-复杂度3 二分查找pta

### 关于二分查找算法在PTA平台上复杂度为3的题目解析

#### 二分查找简介
二分查找是一种高效的搜索算法，适用于已排序的数据序列。其基本原理是在有序数组中寻找特定元素的位置。每次比较都将当前区间分为两部分，从而逐步缩小目标位置所在的范围。

对于复杂度级别的定义，在此假设是指解题难度而非时间空间复杂度。针对这一等级的要求，下面给出一个较为复杂的例子来展示如何运用二分查找解决实际问题：

#### 示例：在一个几乎升序排列的循环移位列表里找到最小值
给定一个已经按升序排序过的整型数组 `nums` ，但是该数组被旋转了一次以上（即某些连续的部分被移到了开头）。例如 `[4,5,6,7,0,1,2]` 。现在需要编写函数找出其中最小的那个数字，并返回它的索引；如果存在多个相同的小数值，则任选其中一个作为结果即可。

这个问题可以通过调整标准版二分查找实现高效求解[^2]:

def findMinIndex(nums):
    low, high = 0, len(nums)-1
    
    while low < high:
        mid = (low + high)//2
        
        # 如果中间点大于最右端说明转折点还在右边
        if nums[mid] > nums[high]:
            low = mid + 1
            
        elif nums[mid] < nums[high]: 
            # 否则就在左边(含mid)，因为此时mid可能是最小值所在处
            high = mid 
            
        else:  
            # 当遇到重复项时无法判断哪边有更小者，只能线性扫描剩余部分
            return min(range(low, high+1), key=lambda x: nums[x])
            
    return low

上述代码实现了对输入条件下的优化处理方式，不仅考虑到了常规情况还兼顾了一些特殊情况比如含有重复元素的情形。通过这种方式可以在O(logn)的时间内完成任务，满足题目需求的同时也体现了较高的技巧性和灵活性。