順序付きリストでの二分探索とは何ですか?

順序付きリストでの半分の検索: 中央の値を比較オブジェクトとして使用します。指定された値が中央の値のキーと等しい場合、検索は成功します。指定された値がキーより小さい場合、検索は成功します。中央のレコードの左半分まで検索が成功すると、検索は中央のレコードの左半分で続行されます。

#この記事の動作環境: Windows 7 システム、Dell G3 コンピューター。

ハーフサーチの概念:

ハーフサーチは二分探索とも呼ばれます。

前提条件は、線形テーブル内のレコードはキーの順序 (小さいものから大きいもの、または大きいものから小さいもの) である必要があり、線形テーブルは順番に格納される必要があります。

半検索の基本的な考え方は次のとおりです: 順序付きリストで、中央の値を比較対象として、指定された値と中央の値のキーが等しい場合、検索は成功します。指定された値が中央のレコードのキーより小さい場合、検索は中央のレコードの左半分で続行されます。指定された値が中央のレコードのキーより大きい場合、検索は実行されます。中央のレコードの右半分に続きます。検索が成功するか、すべての領域にレコードがなく検索が失敗するまで、上記のプロセスを繰り返します。

アルゴリズム実装:

public int Binary_Search(int[] a, int n, int key) {
int low = 1, high = n, mid;
while(low <= high) {
mid = (int)((low + high) / 2);
if(key < a[mid]) {
high = mid - 1;
}
else if(key > a[mid]) {
low = mid + 1;
}
else return mid;
}
return 0;
}

通常、low、high、mid の 3 つのポインターが使用されます。それぞれ、検索領域の左端の値の添字、検索領域の右端の値の添字、および現在の比較値の添字を表します。

時間計算量分析:

半分の検索は、実際には、静的順序付けルックアップ テーブルを 2 つのサブツリーに分割することと同じです。つまり、データの半分だけを見つける必要があります。つまり、検索時の作業量が半分になり、効率が向上します。

関連ビデオの推奨事項: PHP プログラミングの入門から習熟まで

以上が順序付きリストでの二分探索とは何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。