Searching: linear and binary · 検索：線形検索と二項検索
Two ways to search
- Searching means finding where a value is in an array (or saying it is not there).
- Linear search checks every item one by one. It works on any array.
- Binary search is much faster but needs the array to be sorted first.
2つの検索方法
- 検索とは、配列内で値の位置を見つけること（あるいは存在しないことを告げること）です。
- 線形検索は、すべての要素を1つずつ確認します。どんな配列でも機能します。
- 二項検索は遥かに速いですが、まず配列がソート済みであることを要件とします。
Linear search
- Walk from index
0ton - 1, comparing each item to the target. - Return the index the moment you find it. If you reach the end, return
-1. - For an array of
nitems, this looks at up tonof them.
線形探索
- インデックス
0からn - 1までトレースし、各要素をターゲットと比較します。 - 見つかったら即座にインデックスを返します。最後まで辿り着いても見つからない場合は、
-1を返します。 n個の要素を持つ配列に対して、この処理は最大でn個の要素を確認します。
Why sorting enables binary search
- If the array is sorted, you can jump to the middle and compare.
- If the middle is too small, the target must be in the right half; if too big, the left half.
- Each step throws away half the array, so it is very fast (about
log2(n)steps).
ソートが二項検索を可能にする理由
- 配列がソート済みなら、中央にジャンプして比較できます。
- 中央が小さすぎたらターゲットは右半分に、大きすぎたら左半分にあります。
- ステップごとに配列の半分を除外するため、非常に高速です（約
log2(n)ステップ）。
low, high, mid
- Keep two bounds:
low(start) andhigh(end). The middle ismid = low + (high - low) / 2. - If
a[mid]is the target, returnmid. Ifa[mid] < target, movelow = mid + 1; elsehigh = mid - 1. - Stop when
low > high— the target is not there, so return-1.
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を返します。
#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;
}
Common mistakes
- Binary search needs a sorted array.
- Linear search checks each element in turn.
よくあるミス
- 二分探索には整列済みの配列が必要。
- 線形検索は各要素を順番に確認します。
Now you try
- For binary search, assume the array is already sorted. Use
low,high, andmid. - Return
-1when the value is not found. Do not write amain— the checker provides one.
あなたも試してみよう
- 二分探索では、配列が既にソートされていると仮定します。
low、high、midを使用します。 - 値が見つからない場合は
-1を返します。mainを記述してはいけません — チェッカー側で提供しています。
Linear vs binary search · 線形探索と二項探索
Binary search halves the range each step. · 二分探索は、各ステップで範囲を半分にする。
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 not write a main. · int linear_search(const int a[], int n, int target)を完成させて、最初のtargetのインデックスを返すか、配列にない場合は-1を返すようにする。mainは書かない。
Click Run to see the output here. · 実行ボタンをクリックして出力を確認してください。
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 not write a main. · int binary_search(const int a[], int n, int target)を並べ替え済みの配列に対して完成させる。targetのインデックスを返すか、-1を返す。low、high、midを使用する。mainは書かない。
Click Run to see the output here. · 実行ボタンをクリックして出力を確認してください。
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 not write a main. · int first_negative(const int a[], int n)を完成させて、最初の0より小さい要素のインデックスを返すか、存在しない場合は-1を返すようにする。mainは書かない。
Click Run to see the output here. · 実行ボタンをクリックして出力を確認してください。