跳轉至
紙質書（簡體中文版）已發行，詳情請見這裡

# 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 的左邊界。”

1. 這名同學的說法是否正確？數字 2 的左、右邊界分別是多少？請說明理由。
2. 查詢左邊界時，若中點元素等於目標，接下來應繼續搜尋哪一側？
3. 查詢右邊界時又應繼續搜尋哪一側？只需說明方向，無須寫出完整的查詢過程。

參考答案

1. 這名同學的說法不正確。找到一個 2 後立即返回，只能保證找到某一個 2，不能保證找到最左或最右的 2。 本題的左邊界為索引 1，右邊界為索引 3。

2. 查詢左邊界時，即使中點元素等於 2，也要繼續搜尋左側， 例如在雙閉區間寫法中令 `j = m - 1`。

3. 查詢右邊界時，中點元素等於 2 後應繼續搜尋右側， 例如令 `i = m + 1`。

### 3. 不同資料該選哪種搜尋方法

請在“順序查詢、二分搜尋、雜湊表”中，為下面三個場景選擇合適的方法，並說明理由：

1. 在 \(10^7\) 個已經有序且不再變動的整數中反覆查詢，不額外建立其他資料結構；
2. 在頻繁插入、刪除的資料集中反覆判斷某個鍵是否存在，不要求保持有序，也不進行範圍查詢；
3. 在無序陣列中只查詢一次某個值。

參考答案

1. 二分搜尋：資料有序且靜態，\(O(\log n)\) 且無須額外空間。
2. 雜湊表：當雜湊函式能把鍵較均勻地分散到各桶時，插入、刪除和按鍵查詢的平均時間複雜度都是 \(O(1)\)。

3. 直接從頭到尾走訪：只查詢一次時，排序或建立雜湊表都要先處理整個陣列， 並不會減少這一次任務的總工作量。

   選擇取決於資料是否有序、是否允許建立額外結構、查詢次數以及需要執行哪些操作。

## 10.7.2 程式設計練習

### 1. 有序陣列的二分搜尋

給定一個按嚴格遞增順序排列的整數陣列 `nums` 和目標值 `target`。請使用二分搜尋找到 `target`：若存在，返回它的陣列索引；若不存在，返回 -1。

解題提示

1. 初始區間是 left = 0、right = n - 1，非空條件是 left <= right
2. 用 mid = left + (right - left) // 2 計算中點
3. 若 `nums[mid]` 小於 `target`，就把左邊界移到 `mid + 1`；若 `nums[mid]` 大於 `target`，就把右邊界移到 `mid - 1`；相等時立即返回

LeetCode 題目解析

### 2. 有序陣列的插入位置

給定一個按嚴格遞增順序排列的整數陣列 `nums` 和目標值 `target`。

若 `target` 已在陣列中，返回它的索引；否則，返回把 `target` 插入陣列後仍能保持嚴格遞增順序的位置。答案可能是 0，也可能等於陣列長度。請使用二分搜尋。

解題提示

1. 答案可能是 0，也可能是陣列長度 n
2. 使用雙閉區間時，若 `nums[mid]` 大於等於 `target`，就令 `right = mid - 1`，繼續檢查更靠左的位置；否則令 `left = mid + 1`
3. 迴圈結束時 left 就是插入位置

LeetCode

##### 歡迎在評論區留下你的見解、問題或建議