算法模式：改进的二分查找

D瓜哥

2025-03-04

算法

在上一篇文章算法模式：前缀和介绍了前缀和的算法模式。本篇文章，继续介绍数组相关的算法模式：改进的二分查找。

二分查找

二分查找相比每一个学过计算机算法的小伙伴都了解，时间复杂度是： \$\log_2N\$，是一个非常高效的数组查找算法。当然，前提是数组必须有序。过程如下：

图 1. 二分查找

LeetCode 704. 二分查找就是一个标准的二分查找的算法题。代码如下：

/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2024-09-14 19:52:26
 */
public int search(int[] nums, int target) {
  int left = 0, right = nums.length - 1;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] == target) {
      return mid;
    } else if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return -1;
}

除了在排序数组中查找特定的值，二分查找还可以用于找边界和在旋转数组中查值。

找边界：LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置

LeetCode - 34. 在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 \$log_2n\$ 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

提示：

0 <= nums.length <= 10⁵
-10⁹<= nums[i] <= 10⁹
nums 是一个非递减数组
-10⁹<= target <= 10⁹

思路分析

要求时间复杂度为 \$log_2n\$ 的算法，那么很显然这就得上二分查找。

但是，课本上及大多数资料里的二分查找都是查找确定值的，没有查找边界的，该怎么办呢？这就需要对二分查找做一些小小的改进了：

在 num[mid] == target 时，如果查找的左边界，那么，目标索引在当前 mid 的左侧，应该将右侧的指针 right 移动到 mid 左边，即 right = mid - 1。
在 num[mid] == target 时，如果查找的右边界，那么，目标索引在当前 mid 的右侧，应该将左侧的指针 left 移动到 mid 右边，即 left = mid + 1。

分析完毕，直接上代码：

/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2025-03-04 21:02:59
 */
public int[] searchRange(int[] nums, int target) {
  int left = binarySearchLeft(nums, target);
  if (left == -1) {
    return new int[]{-1, -1};
  }
  int right = binarySearchRight(nums, target);
  return new int[]{left, right};
}

private int binarySearchLeft(int[] nums, int target) {
  int left = 0;
  int right = nums.length - 1;
  // 使用 result 变量，省去很多繁琐的判断
  int result = -1;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] < target) {
      left = mid + 1;
    } else if (target < nums[mid]) {
      right = mid - 1;
    } else {
      // 注意：找左边界，要收缩右指针
      right = mid - 1;
      result = mid;
    }
  }
  return result;
}

private int binarySearchRight(int[] nums, int target) {
  int left = 0;
  int right = nums.length - 1;
  // 使用 result 变量，省去很多繁琐的判断
  int result = -1;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] < target) {
      left = mid + 1;
    } else if (target < nums[mid]) {
      right = mid - 1;
    } else {
      // 注意：找右边界，要搜索左指针
      left = mid + 1;
      result = mid;
    }
  }
  return result;
}

binarySearchLeft 和 binarySearchRight 有很多重复代码，可以优化一下：

/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2025-03-05 14:11:58
 */
public int[] searchRange(int[] nums, int target) {
  int left = binarySearch(nums, target, true);
  if (left == -1) {
    return new int[]{-1, -1};
  }
  int right = binarySearch(nums, target, false);
  return new int[]{left, right};
}

private int binarySearch(int[] nums, int target, boolean isLeft) {
  int left = 0;
  int right = nums.length - 1;
  // 使用 result 变量，省去很多繁琐的判断
  int result = -1;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] < target) {
      left = mid + 1;
    } else if (target < nums[mid]) {
      right = mid - 1;
    } else {
      if (isLeft) {
        // 注意：找左边界，要收缩右指针
        right = mid - 1;
      } else {
        // 注意：找右边界，要搜索左指针
        left = mid + 1;
      }
      result = mid;
    }
  }
  return result;
}

旋转数组查值：33. 搜索旋转排序数组

LeetCode - 33. 搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= 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 ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 \$log_2N\$ 的算法解决此问题。

示例 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⁴<= nums[i] <= 10⁴
nums 中的每个值都 独一无二
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-10⁴<= target <= 10⁴

思路分析

由于这是一个旋转有序数组，在使用二分查找算法时，应该将重点放在有序部分，在有序部分去查找目标值，如果目标值不在有序部分的范围内，则去另外一部分去查找。至于为什么在有序部分查找，是因为有序部分判断条件比较简单。具体看代码：

/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2025-03-05 14:11:58
 */
public int search(int[] nums, int target) {
  int left = 0, right = nums.length - 1;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] == target) {
      return mid;
    }
    if (nums[0] <= nums[mid]) {
      // 由于 nums[0] <= nums[mid]，所以，这个分支处理的是前面有序的情况
      // --------------------------------------------
      // 上面已经判断过 nums[mid] 和 target 是否相等，
      // 这里就不需要再处理相等情况，所以，可以直接去 mid 左右的索引
      // 该分支前面有序，只需要在有序数组里去查找即可，不满足要求，则在另外一部分里。
      if (nums[0] <= target && target < nums[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    } else {
      // 上面只处理前面有序的情况，那么这里就可能是后面有序的情况。
      // --------------------------------------------
      // 上面已经判断过 nums[mid] 和 target 是否相等，
      // 这里就不需要再处理相等情况，所以，可以直接去 mid 左右的索引
      // 同理，这里也只在有序的数组里去查找，不满足要求则去另外一部分查找。
      if (nums[mid] < target && target <= nums[nums.length - 1]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }
  return -1;
}