mirror of
https://github.com/krahets/hello-algo.git
synced 2026-11-01 05:05:03 +08:00
7257641e0e
* Retranslate the complete Japanese online edition from Chinese * Fit Japanese homepage labels and localize heading permalinks * Point Japanese contribution instructions to the Japanese preview * Replace locale conditionals with multilingual UI tables
96 lines
5.6 KiB
Markdown
96 lines
5.6 KiB
Markdown
# 練習問題
|
|
|
|
## 知識の確認
|
|
|
|
### 二分探索で探索区間を狭めるには
|
|
|
|
整列済み配列 `[2, 5, 8, 12, 16, 23, 38]` から 16 を探します。
|
|
両端を含む閉区間 `[i, j]` を使い、中点は
|
|
$m=i+(j-i)/2$（切り捨て）とします。
|
|
|
|
見つかるまで、各反復の `(i, j, m)`、中点の要素、
|
|
次に区間をどう狭めるかを書いてください。
|
|
|
|
??? success "解答例"
|
|
|
|
各反復の探索過程は、次のとおりです。
|
|
|
|
| 反復 | `(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 を返します |
|
|
|
|
配列は整列済みなので、中点の値が目的の値より小さければ、中点とその左側を除外できます。
|
|
中点の値が目的の値より大きければ、中点とその右側を除外できます。
|
|
|
|
### 重複する要素の左右の境界
|
|
|
|
配列 `[1, 2, 2, 2, 4, 6]` から 2 を探します。
|
|
ある生徒が二分探索でインデックス 2 に目的の値を見つけ、すぐに返して、
|
|
「インデックス 2 が、2 の左境界だ」と言いました。
|
|
|
|
<!-- numbered-subquestions -->
|
|
|
|
1. この生徒の発言は正しいですか。2 の左右の境界はそれぞれどこですか。理由も説明してください。
|
|
2. 左境界を探す場合、中点の要素が目的の値と等しかったら、次はどちら側を探し続けますか。
|
|
3. 右境界を探す場合は、どちら側を探し続けますか。方向だけを説明し、探索過程全体を書く必要はありません。
|
|
|
|
??? success "解答例"
|
|
|
|
1. この生徒の発言は正しくありません。一つの 2 を見つけてすぐに返すと、どれか一つの 2 を見つけたことしか保証できず、最も左や右の 2 を見つけたとは限りません。
|
|
この問題の左境界はインデックス 1、右境界はインデックス 3 です。
|
|
|
|
2. 左境界を探すときは、中点の要素が 2 と等しくても、左側を探し続けます。
|
|
例えば、両端を含む閉区間を使う場合は `j = m - 1` とします。
|
|
|
|
3. 右境界を探すときは、中点の要素が 2 と等しかったら、右側を探し続けます。
|
|
例えば `i = m + 1` とします。
|
|
|
|
### データに合った探索方法を選ぶ
|
|
|
|
次の各場面に適した方法を「線形探索、二分探索、ハッシュテーブル」から選び、理由を説明してください。
|
|
|
|
<!-- numbered-subquestions -->
|
|
|
|
1. 整列済みで今後変化しない $10^7$ 個の整数を繰り返し探索します。ほかのデータ構造は追加で作りません。
|
|
2. 挿入と削除が頻繁なデータ集合で、キーの有無を繰り返し調べます。整列状態を保つ必要はなく、範囲探索もしません。
|
|
3. 未整列配列から、ある値を一回だけ探します。
|
|
|
|
??? success "解答例"
|
|
|
|
1. 二分探索です。データが整列済みで変化せず、$O(\log n)$ 時間で探索でき、追加の領域も不要です。
|
|
2. ハッシュテーブルです。ハッシュ関数がキーを各バケットへ比較的均等に分散できる場合、挿入、削除、キーによる探索の平均時間計算量は、いずれも $O(1)$ です。
|
|
3. 先頭から末尾まで直接走査します。一回しか探さない場合、ソートやハッシュテーブルの構築では、先に配列全体を処理する必要があり、
|
|
その一回の作業の総量は減りません。
|
|
|
|
選択は、データが整列済みか、追加の構造を作れるか、照会回数はいくつか、どの操作が必要かによって決まります。
|
|
|
|
## プログラミング演習
|
|
|
|
### 整列済み配列の二分探索
|
|
|
|
狭義の昇順に並んだ整数配列 `nums` と目的の値 `target` が与えられます。二分探索で `target` を探し、存在すれば配列内のインデックスを、存在しなければ -1 を返してください。
|
|
|
|
??? tip "解くためのヒント"
|
|
|
|
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](https://leetcode.com/problems/binary-search/){ .rounded-button .exercise-button target="_blank" rel="noopener noreferrer" }
|
|
|
|
### 整列済み配列への挿入位置
|
|
|
|
狭義の昇順に並んだ整数配列 `nums` と目的の値 `target` が与えられます。
|
|
|
|
`target` が配列にあれば、そのインデックスを返してください。なければ、`target` を挿入しても狭義の昇順を保てる位置を返してください。答えは 0 の場合も、配列の長さと等しい場合もあります。二分探索を使ってください。
|
|
|
|
??? tip "解くためのヒント"
|
|
|
|
1. 答えは 0 の場合も、配列の長さ n の場合もあります
|
|
2. 両端を含む閉区間を使う場合、`nums[mid]` が `target` 以上なら `right = mid - 1` として、さらに左を調べます。そうでなければ `left = mid + 1` とします
|
|
3. ループが終わったときの left が挿入位置です
|
|
|
|
[LeetCode](https://leetcode.com/problems/search-insert-position/){ .rounded-button .exercise-button target="_blank" rel="noopener noreferrer" }
|