搜索旋转排序数组题实现错误排查（要求O(log n)复杂度）

题目要求 #

存在一个元素值互不相同的升序排列整数数组nums，在传入函数前，nums可能会在未知的枢轴（pivot）下标k (1 <= k < nums.length)处发生旋转，旋转后的数组结构为[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标从0开始计数）。例如原升序数组[0,1,2,4,5,6,7]在枢轴下标3处旋转后，得到数组[4,5,6,7,0,1,2]。
请基于旋转后的数组nums和整数目标值target实现算法：若target存在于nums中则返回其对应下标，若不存在则返回-1，要求算法的时间复杂度必须为O(log n)。

测试示例 #

• 示例1：
  输入：nums = [4,5,6,7,0,1,2], target = 0
  输出：4
• 示例2：
  输入：nums = [4,5,6,7,0,1,2], target = 3
  输出：-1
• 示例3：
  输入：nums = [1], target = 0
  输出：-1

约束条件 #

1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
nums中所有元素值唯一，是升序数组经过0次或1次旋转得到的
-10^4 <= target <= 10^4

提交的问题代码 #

class Solution(object):
    def search(self, arr, x):
        l=0
        u=len(arr)-1
        m=0
    
        while(l<=u):
            m=(u+l)//2

            if(arr[m]==x):
                return m
            elif(arr[m]<x):
                l=m+1  
            else:
                u=m-1

        return -1

错误原因 #

现有代码是标准二分查找实现，适用前提是数组全局升序。旋转后的数组仅满足两个分段各自升序，不满足全局有序，因此普通二分的区间收缩逻辑会出错：比如示例1中第一次取到中点值7时，普通二分会判定目标值0小于7，直接将搜索区间收缩到左半段，但0实际位于右半段，最终导致漏判返回-1。

修正方案 #

旋转排序数组的二分查找核心逻辑是：每次取中点后，先判断左、右哪个分段是严格有序的，再判断目标值是否落在有序分段的数值范围内，以此决定区间收缩方向：

1. 若arr[l] <= arr[m]，说明左半段[l, m]为严格升序段：
   • 若满足arr[l] <= x < arr[m]，说明目标在左半段，将右边界收缩为m-1
   • 否则目标在右半段，将左边界收缩为m+1
2. 否则说明右半段[m, u]为严格升序段：
   • 若满足arr[m] < x <= arr[u]，说明目标在右半段，将左边界收缩为m+1
   • 否则目标在左半段，将右边界收缩为m-1

修正后的可运行代码如下：

class Solution(object):
    def search(self, arr, x):
        l = 0
        u = len(arr) - 1
        while l <= u:
            m = (l + u) // 2
            if arr[m] == x:
                return m
            # 左半段有序
            if arr[l] <= arr[m]:
                if arr[l] <= x < arr[m]:
                    u = m - 1
                else:
                    l = m + 1
            # 右半段有序
            else:
                if arr[m] < x <= arr[u]:
                    l = m + 1
                else:
                    u = m - 1
        return -1

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