このページには最新のブラウザ(SharedArrayBuffer対応)が必要です。Chrome、Edge、Firefox、Safariを最新バージョンに更新してください。
値の検索
- 一般的なタスクとして、配列に特定の値が含まれているか、そしてどこにあるかを検索する。
- 一般的な答えは、見つけた場所のインデックスであり、存在しない場合は
-1。 - 2つの方法学ぶ:線形探索(任意の配列で動作)と二分探索(整列済みの配列が必要だが、はるかに速い)。
線形探索
- インデックス
0から末尾まで各アイテムを見る。 - アイテムがターゲットに一致すれば、直ちにそのインデックスを返す。
- ループが終了しても一致が見つからなければ、
-1を返す。
English
public class Main {
public static void main(String[] args) {
int[] a = {4, 8, 15, 16, 23};
int target = 15;
int found = -1;
for (int i = 0; i < a.length; i++) {
if (a[i] == target) {
found = i;
break; // stop early, we have it
}
}
System.out.println(found); // 2
}
}
線形探索の速度
- 最悪の場合(値が最後にある、または存在しない場合)、すべてのアイテムを確認する。
n個の項目を持つリストに対して最大n回のチェックを行う。これをリニア時間_complexity_という。- 小さな配列では問題ない。巨大な整列済み配列では、より良い方法がある。
二分探索には整列済み配列が必要
- 二分探索は、配列が既に整列されている(小さい順から大きい順)場合にのみ機能する。
- 真ん中のアイテムをチェックし、ステップごとに配列の半分を除外していく。
- これは遥かに速いです:百万個のアイテムに対しては、百万回のチェックではなく約 20 回のチェックで済みます。
二分探索の考え方
- 2つの境界を維持する:
low(開始)とhigh(終了)。 - 真ん中のインデックス
mid = (low + high) / 2を見る。 a[mid]がターゲットに一致すれば、midを返す。a[mid]が小さすぎる場合、ターゲットは右側にあるので、low = mid + 1を更新する。a[mid]が大きすぎる場合、ターゲットは左側にあるので、high = mid - 1を更新する。lowがhighを超えたら停止;値が存在しない場合、-1を返す。
English
public class Main {
public static void main(String[] args) {
int[] a = {2, 5, 8, 12, 16, 23, 38}; // sorted!
int target = 16;
int low = 0;
int high = a.length - 1;
int found = -1;
while (low <= high) {
int mid = (low + high) / 2;
if (a[mid] == target) {
found = mid;
break;
} else if (a[mid] < target) {
low = mid + 1; // go right
} else {
high = mid - 1; // go left
}
}
System.out.println(found); // 4
}
}
値が存在しない場合
- 両方の探索は、ターゲットが配列に含まれない場合に
-1を返す。 - 二分探索では、
low > high— 境界が交差した時点でループが終了するため、残りの検索範囲がない。 - 探索を呼び出すコードでは、必ず
-1のケースを処理する。
English
public class Main {
public static void main(String[] args) {
int[] a = {2, 5, 8, 12}; // sorted
int target = 7; // not in the array
int low = 0;
int high = a.length - 1;
int found = -1;
while (low <= high) {
int mid = (low + high) / 2;
if (a[mid] == target) {
found = mid;
break;
} else if (a[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
System.out.println(found); // -1
}
}
よくあるミス
- 二分探索には整列済みの配列が必要。
- 線形探索はO(n);二分探索はO(log n)。
あなたも試してみよう
- 各タスクはクラス骨組みを事前入力しています。main 内にコードを書くか、表示されたメソッドを完成させてください。
- Check answerを使用して提供されたテストでコードをコンパイルし、結果を確認してください。スタートファイルに表示されているクラスとメソッドのインターフェースを維持してください。
- コードはサーバー上でコンパイル・実行されるため、初回実行でも高速です。
探索
線形探索と二項探索
二項検索はステップごとに範囲を半分に減らす — 大幅にチェック数を削減します。
難易度 3/5 · 200 コイン + 今日初回達成時の小ボーナス
linearSearch(int[] a, int target) を完成させ、target に等しい最初のアイテムのインデックスを返し、または存在しない場合は -1 を返しなさい。インデックス 0 以降のアイテムをチェックします。
実行ボタンをクリックして出力を確認してください。
難易度 3/5 · 200 コイン + 今日初回達成時の小ボーナス
整列済みの配列に対するbinarySearch(int[] a, int target) を完成させなさい。low/high の境界を使い、ステップごとに中央をチェックします。target のインデックスを返し、または欠落している場合は -1 を返します。
実行ボタンをクリックして出力を確認してください。
難易度 3/5 · 200 コイン + 今日初回達成時の小ボーナス
countOccurrences(int[] a, int target) を完成させ、target が a 内でいくつ出現するかを返すようにしなさい(線形スキャン)。全く出現しない場合は 0 を返します。
実行ボタンをクリックして出力を確認してください。