このページには最新のブラウザ(SharedArrayBuffer対応)が必要です。Chrome、Edge、Firefox、Safariを最新バージョンに更新してください。
2つの検索方法
- 検索とは、配列内で値の位置を見つけること(あるいは存在しないことを告げること)です。
- 線形検索は、すべての要素を1つずつ確認します。どんな配列でも機能します。
- 二項検索は遥かに速いですが、まず配列がソート済みであることを要件とします。
線形探索
- インデックス
0からn - 1までトレースし、各要素をターゲットと比較します。 - 見つかったら即座にインデックスを返します。最後まで辿り着いても見つからない場合は、
-1を返します。 n個の要素を持つ配列に対して、この処理は最大でn個の要素を確認します。
ソートが二項検索を可能にする理由
- 配列がソート済みなら、中央にジャンプして比較できます。
- 中央が小さすぎたらターゲットは右半分に、大きすぎたら左半分にあります。
- ステップごとに配列の半分を除外するため、非常に高速です(約
log2(n)ステップ)。
low, high, mid
- 2つの境界を維持します:
low(開始)とhigh(終了)。中央はmid = low + (high - low) / 2です。 a[mid]がターゲットならmidを返します。a[mid] < targetならlow = mid + 1を移動させ;そうでなければhigh = mid - 1。low > highになったら停止—ターゲットは存在しないので、-1を返します。
English
#include <stdio.h>
int main(void) {
int a[] = {1, 3, 5, 7, 9}; // sorted!
int target = 7, lo = 0, hi = 4, found = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == target) { found = mid; break; }
if (a[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
printf("%d\n", found); // 3
return 0;
}
よくあるミス
- 二分探索には整列済みの配列が必要。
- 線形検索は各要素を順番に確認します。
あなたも試してみよう
- 二分探索では、配列が既にソートされていると仮定します。
low、high、midを使用します。 - 値が見つからない場合は
-1を返します。mainを記述してはいけません — チェッカー側で提供しています。
探索
線形探索と二項探索
Binary search halves the range each step.
難易度 3/5 · 200 コイン + 今日初回達成時の小ボーナス
Complete int linear_search(const int a[], int n, int target) so it returns the index of the first target, or -1 if it is not in the array. Do ~ではない write a main.
実行ボタンをクリックして出力を確認してください。
難易度 3/5 · 200 コイン + 今日初回達成時の小ボーナス
Complete int binary_search(const int a[], int n, int target) for a sorted array. Return the index of target, or -1. Use low, high, and mid. Do ~ではない write a main.
実行ボタンをクリックして出力を確認してください。
難易度 3/5 · 200 コイン + 今日初回達成時の小ボーナス
Complete int first_negative(const int a[], int n) so it returns the index of the first item less than 0, or -1 if there is none. Do ~ではない write a main.
実行ボタンをクリックして出力を確認してください。