二分查找题目：二分查找

题目

标题和出处

标题：二分查找

出处：704. 二分查找

难度

2 级

题目描述

要求

给定一个按升序排序的整数数组 $\text{nums}$ 和一个整数 $\text{target}$，在 $\text{nums}$ 中查找 $\text{target}$。如果 $\text{target}$ 存在，返回其下标。否则，返回 $\text{-1}$。

要求时间复杂度是 $\text{O(log n)}$。

示例

示例 1：

输入：$\text{nums = [-1,0,3,5,9,12], target = 9}$
输出：$\text{4}$
解释：$\text{9}$ 在 $\text{nums}$ 中，下标为 $\text{4}$。

示例 2：

输入：$\text{nums = [-1,0,3,5,9,12], target = 2}$
输出：$\text{-1}$
解释：$\text{2}$ 不在 $\text{nums}$ 中，因此返回 $\text{-1}$。

数据范围

• $\text{1}\le \text{nums.length}\le {\text{10}}^{\text{4}}$
• ${\text{-10}}^{\text{4}}<\text{nums[i], target}<{\text{10}}^{\text{4}}$
• $\text{nums}$ 中的所有整数各不相同
• $\text{nums}$ 按升序排序

前言

这道题是最简单的二分查找。给定的数组按升序排序，所有的元素各不相同，因此如果目标值存在则其下标唯一。

用 $\text{low}$ 和 $\text{high}$ 分别表示二分查找的下标范围的下界和上界，初始时 $\text{low}$ 和 $\text{high}$ 分别为数组的最小下标和最大下标。每次查找时，取 $\text{mid}$ 为 $\text{low}$ 和 $\text{high}$ 的平均数向下取整，判断下标 $\text{mid}$ 处的数和目标值的大小关系，调整查找的下标范围。

• 如果 $\text{nums}[\text{mid}]=\text{target}$，则找到目标值，其下标为 $\text{mid}$。

• 如果 $\text{nums}[\text{mid}]>\text{target}$，则如果目标值存在，其下标一定小于 $\text{mid}$，因此在下标范围 $[\text{low},\text{mid}-1]$ 中继续查找。

• 如果 $\text{nums}[\text{mid}]<\text{target}$，则如果目标值存在，其下标一定大于 $\text{mid}$，因此在下标范围 $[\text{mid}+1,\text{high}]$ 中继续查找。

如果查找的过程中出现 $\text{low}>\text{high}$，则目标值不存在，返回 $-1$。

每次查找都可以将查找的下标范围减少一半，因此当数组的长度是 $n$ 时，二分查找的时间复杂度是 $O(\log n)$。

二分查找可以使用递归或迭代实现。

解法一

思路和算法

使用递归实现二分查找时，需要在递归调用时指定查找的下标范围。每次查找时，如果当前查找的下标处的元素值等于目标值则返回当前查找的下标，否则根据元素值与目标值的大小关系调整查找的下标范围，然后在新的下标范围中继续查找。

递归调用有以下两个终止条件。

1. 如果当前的下标范围是空，即 $\text{low}>\text{high}$，则目标值不存在，返回 $-1$。

2. 如果当前查找的下标处的元素值等于目标值，则返回当前查找的下标。

代码

class Solution {public int search(int[] nums, int target) {return search(nums, target, 0, nums.length - 1);}public int search(int[] nums, int target, int low, int high) {if (low > high) {return -1;}int mid = low + (high - low) / 2;if (nums[mid] == target) {return mid;} else if (nums[mid] > target) {return search(nums, target, low, mid - 1);} else {return search(nums, target, mid + 1, high);}}
}

复杂度分析

• 时间复杂度：$O(\log n)$，其中 $n$ 是数组 $\text{nums}$ 的长度。二分查找的次数是 $O(\log n)$，每次查找的时间是 $O(1)$，时间复杂度是 $O(\log n)$。

• 空间复杂度：$O(\log n)$，其中 $n$ 是数组 $\text{nums}$ 的长度。空间复杂度主要取决于递归调用栈空间，递归调用栈的层数是 $O(\log n)$。

解法二

思路和算法

使用迭代实现二分查找时，需要在二分查找的过程中维护查找的下标范围。每次查找时，如果当前查找的下标处的元素值等于目标值则返回当前查找的下标，否则根据元素值与目标值的大小关系调整查找的下标范围，然后在新的下标范围中继续查找。

查找的过程中，如果当前查找的下标处的元素值等于目标值，则返回当前查找的下标。如果出现 $\text{low}>\text{high}$，则目标值不存在，返回 $-1$。

代码

class Solution {public int search(int[] nums, int target) {int low = 0, high = nums.length - 1;while (low <= high) {int mid = low + (high - low) / 2;if (nums[mid] == target) {return mid;} else if (nums[mid] > target) {high = mid - 1;} else {low = mid + 1;}}return -1;}
}

复杂度分析

• 时间复杂度：$O(\log n)$，其中 $n$ 是数组 $\text{nums}$ 的长度。二分查找的次数是 $O(\log n)$，每次查找的时间是 $O(1)$，时间复杂度是 $O(\log n)$。

• 空间复杂度：$O(1)$。

拓展问题

最简单的二分查找中，如果目标值不存在则返回 $-1$。当目标值不存在时，定义目标值在数组中的插入位置如下：目标值 $\text{target}$ 在数组 $\text{nums}$ 中的插入位置是 $\text{index}$，则 $\text{nums}[\text{index}-1]<\text{target}<\text{nums}[\text{index}]$。这里假设 $\text{nums}[-1]=-\infty$，$\text{nums}[n]=+\infty$，其中 $n$ 是数组 $\text{nums}$ 的长度。

当目标值不存在时，是否可以使用返回值表示目标值在数组中的插入位置？

在二分查找的过程中，如果 $\text{nums}[\text{mid}]<\text{target}$，则将 $\text{low}$ 更新为 $\text{mid}+1$，因此在二分查找结束之后有 $\text{nums}[\text{low}]\ge \text{target}$。当目标值不存在时，二分查找结束之后有 $\text{nums}[\text{low}]>\text{target}$。又由于当 $\text{nums}[\text{mid}]\ge \text{target}$ 时不可能将 $\text{low}$ 更新为比 $\text{mid}$ 大的值，因此在二分查找结束之后有 $\text{nums}[\text{low}-1]<\text{target}$。

因此在二分查找结束之后有 $\text{nums}[\text{low}-1]<\text{target}<\text{nums}[\text{low}]$，$\text{low}$ 即为目标值在数组中的插入位置。

当目标值不存在时，为了使返回值同时能反映目标值不存在以及表示目标值在数组中的插入位置，返回值可以是 $-\text{low}-1$。

用 $x$ 表示二分查找的返回值。当 $x\ge 0$ 时，目标值在数组中的下标 $x$ 处；当 $x<0$ 时，目标值不在数组中，插入位置是 $-x-1$。