10.7 演習¶

10.7.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 を返す

配列はソート済みなので、中点の値が目的の値より小さければ、中点とその左側を除外できます。中点の値が目的の値より大きければ、中点とその右側を除外できます。

配列 [1, 2, 2, 2, 4, 6] から数値 2 を探索します。ある生徒は、二分探索でインデックス 2 に目的の値を見つけるとすぐに返し、次のように言いました。「インデックス 2 が数値 2 の左端境界です。」

解答

この生徒の説明は正しくありません。2 を 1 つ見つけてすぐに返す方法では、いずれかの 2 を見つけたことしか保証できず、最も左または最も右の 2 だとは限りません。この問題の左端境界はインデックス 1、右端境界はインデックス 3 です。
左端境界を探索するときは、中点の要素が 2 と等しくても、引き続き左側を探索します。たとえば、両閉区間を使う場合は j = m - 1 とします。
右端境界を探索するときは、中点の要素が 2 と等しければ、引き続き右側を探索します。たとえば、i = m + 1 とします。

「線形探索、二分探索、ハッシュテーブル」から、次の 3 つの場面に適した方法を選び、理由を説明してください。

解答

二分探索です。データがソート済みで変更されないため、追加の空間を使わず \(O(\log n)\) で探索できます。
ハッシュテーブルです。ハッシュ関数によってキーが各バケットへほぼ均等に分散される場合、挿入、削除、キーによる探索の平均時間計算量はいずれも \(O(1)\) です。
先頭から末尾まで直接走査します。1 回しか探索しない場合、ソートやハッシュテーブルの作成でも、最初に配列全体を処理する必要があるため、この 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 へ移します。等しければすぐに返します

重複なく昇順に並んだ整数配列 nums と目的の値 target が与えられます。

target がすでに配列にあれば、そのインデックスを返します。なければ、target を挿入した後も重複のない昇順を保てる位置を返します。答えは 0 の場合も、配列の長さと等しい場合もあります。二分探索を使って求めてください。

解法のヒント

答えは 0 の場合も、配列の長さ n の場合もあります
両閉区間を使う場合、nums[mid] が target 以上なら right = mid - 1 とし、さらに左の位置を調べます。そうでなければ left = mid + 1 とします
ループが終了した時点で、left が挿入位置です