10.7 练习¶
10.7.1 知识巩固¶
1. 二分查找怎样缩小搜索区间¶
在有序数组 [2, 5, 8, 12, 16, 23, 38] 中查找 16。
使用双闭区间 [i, j]，中点为
\(m=i+(j-i)/2\)（向下取整）。
请写出每轮的 (i, j, m)、中点元素，以及下一步如何缩小区间，
直到找到目标。
参考答案
每轮查找过程如下：
| 轮次 | (i, j, m) |
中点元素 | 下一步 |
|---|---|---|---|
| 1 | (0, 6, 3) |
12 | 12 < 16，令 i = 4 |
| 2 | (4, 6, 5) |
23 | 23 > 16，令 j = 4 |
| 3 | (4, 4, 4) |
16 | 找到目标，返回索引 4 |
数组有序，所以中点值小于目标时可以排除中点及其左侧； 中点值大于目标时可以排除中点及其右侧。
2. 重复元素的左右边界¶
在数组 [1, 2, 2, 2, 4, 6] 中查找数字 2。
一名同学用二分查找在索引 2 找到目标后立即返回，并说：
“索引 2 就是数字 2 的左边界。”
- 这名同学的说法是否正确？数字 2 的左、右边界分别是多少？请说明理由。
- 查找左边界时，若中点元素等于目标，接下来应继续搜索哪一侧？
- 查找右边界时又应继续搜索哪一侧？只需说明方向，无须写出完整的查找过程。
参考答案
-
这名同学的说法不正确。找到一个 2 后立即返回，只能保证找到某一个 2，不能保证找到最左或最右的 2。 本题的左边界为索引 1，右边界为索引 3。
-
查找左边界时，即使中点元素等于 2，也要继续搜索左侧， 例如在双闭区间写法中令
j = m - 1。 -
查找右边界时，中点元素等于 2 后应继续搜索右侧， 例如令
i = m + 1。
3. 不同数据该选哪种搜索方法¶
请在“顺序查找、二分查找、哈希表”中，为下面三个场景选择合适的方法，并说明理由：
- 在 \(10^7\) 个已经有序且不再变动的整数中反复查找，不额外建立其他数据结构；
- 在频繁插入、删除的数据集中反复判断某个键是否存在，不要求保持有序，也不进行范围查找；
- 在无序数组中只查找一次某个值。
参考答案
- 二分查找：数据有序且静态，\(O(\log n)\) 且无须额外空间。
- 哈希表：当哈希函数能把键较均匀地分散到各桶时，插入、删除和按键查找的平均时间复杂度都是 \(O(1)\)。
-
直接从头到尾遍历：只查找一次时，排序或建立哈希表都要先处理整个数组， 并不会减少这一次任务的总工作量。
选择取决于数据是否有序、是否允许建立额外结构、查询次数以及需要执行哪些操作。
10.7.2 编程练习¶
1. 有序数组的二分查找¶
给定一个按严格递增顺序排列的整数数组 nums 和目标值 target。请使用二分查找找到 target：若存在，返回它的数组索引；若不存在，返回 -1。
解题提示
- 初始区间是 left = 0、right = n - 1，非空条件是 left <= right
- 用 mid = left + (right - left) // 2 计算中点
- 若
nums[mid]小于target，就把左边界移到mid + 1；若nums[mid]大于target，就把右边界移到mid - 1；相等时立即返回
2. 有序数组的插入位置¶
给定一个按严格递增顺序排列的整数数组 nums 和目标值 target。
若 target 已在数组中，返回它的索引；否则，返回把 target 插入数组后仍能保持严格递增顺序的位置。答案可能是 0，也可能等于数组长度。请使用二分查找。
解题提示
- 答案可能是 0，也可能是数组长度 n
- 使用双闭区间时，若
nums[mid]大于等于target，就令right = mid - 1，继续检查更靠左的位置；否则令left = mid + 1 - 循环结束时 left 就是插入位置