旋转排序数组

旋转排序数组有什么结构？

• 旋转后数组由两段升序组成, 第一段整体大于第二段;
• 最小值是第二段的第一个元素;
• 未旋转时可看作只有一段升序, 最小值在首位;
• 统一口径: 任取 mid, 总有一侧是有序的;

如何求旋转数组的最小值？

• 比较 nums[mid] 与 nums[right];
  • nums[mid] > nums[right]: 最小值不可能在 mid 左侧, left = mid + 1;
  • nums[mid] < nums[right]: 最小值在 mid 或 mid 左侧, right = mid;
  • 两者相等且元素可能有重复: 无法判断方向, 直接 right -= 1;
• 相等时 right 左移是安全的: mid < right, 即使 mid 是最小值也仍在区间内;

function findMin(nums: number[]): number {
  let start = 0;
  let end = nums.length - 1;
  while (start < end) {
    const mid = Math.floor((start + end) / 2);
    if (nums[mid] < nums[end]) end = mid;
    else if (nums[mid] > nums[end]) start = mid + 1;
    else end -= 1;
  }
  return nums[start];
}

• 无重复元素时不会进入相等分支, 时间复杂度 O(log n);
• 有重复元素时相等分支每轮只排除一个元素, 最差 O(n);

如何在旋转数组中查找目标值？

• 每轮先判断 mid 落在左段还是右段;
• nums[mid] === target 直接返回;
• nums[mid] > nums[right]: mid 在左段, 若 target 落在 [left, mid] 则 right = mid, 否则 left = mid + 1;
• 否则 mid 在右段, 若 target 落在 [mid, right] 则 left = mid + 1, 否则 right = mid;
• 循环结束后还需在 left 处复核一次;

function searchRotated(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length - 1;
  while (left < right) {
    const mid = Math.floor(left + (right - left) / 2);
    if (nums[mid] === target) return mid;
    else if (nums[mid] > nums[right]) {
      if (target >= nums[left] && target <= nums[mid]) right = mid;
      else left = mid + 1;
    } else {
      if (target >= nums[mid] && target <= nums[right]) left = mid + 1;
      else right = mid;
    }
  }
  return nums[left] === target ? left : -1;
}

• 时间复杂度: O(log n);
• 空间复杂度: O(1);