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 就是插入位置