バイナリ検索アルゴリズムと時間計算量について簡単に説明し、バイナリ検索アルゴリズムを実装する

[[432404]]

バイナリ検索は、バイナリ検索アルゴリズムとも呼ばれ、シンプルで理解しやすい高速検索アルゴリズムです。たとえば、0 から 100 までの数字をランダムに書いて、何を書いたかを推測してもらいます。あなたが推測するたびに、その推測が高すぎるか低すぎるかを、あなたが正しく推測するまでお伝えします。

このアルゴリズムでは、検索対象の配列がソートされている必要があり、実装手順は次のとおりです。

• 配列の中央の数字を選択する
• 検索番号は中央の番号と比較されます。中央の番号より小さい場合は、中央の番号の左側のサブ配列を検索します。中央の番号より大きい場合は、中央の番号の右側のサブ配列を検索します。等しい場合は、検索が成功したと返されます。
• 検索が成功または失敗するまで、前の手順を繰り返します。

関数binarySearch(items, item) {
    var 低 = 0,
        高さ = アイテムの長さ - 1、
        中間、要素
    （低<=高）の間{
        中間 = Math.floor((low+high)/2)
        elem = アイテム[mid]
        if(要素 < 項目) {
            低 = 中 + 1
        }そうでない場合 (要素 > 項目) {
            高 = 中 - 1
        }それ以外{
戻る途中
        }
    }
 -1を返す
} 
 
 // テスト
var arr = [2,3,1,4]
 // クイックソート
クイックソート(arr) 
 
バイナリサーチ(arr, 3)
 // 2 
 
バイナリサーチ(arr, 5)
 // -1

テスト成功

バイナリ検索のエラーが発生しやすいポイント:

• ループ終了条件はlow <= highです。<=であることに注意してください。
• midの値はMath.floor((low+high)/2)です。
• 低 高 更新されるたびに、低 = 中 + 1 高 = 中 - 1

バイナリ検索の制限:

• 対象オブジェクトは配列構造であり、要素は添え字を通じてランダムにアクセスされる。
• 配列は順番どおりでなければならない
• 配列が小さすぎて適していません。順次検索を使用してください。
• 配列が長すぎるのは適切ではありません。配列には連続したメモリ空間が必要であり、配列が長すぎると保存に適しません。

時間計算量: O(logn)

空間計算量: O(1)

リートコード: https://leetcode-cn.com/problems/binary-search/solution/er-fen-cha-zhao-by-user7746o/