【PHPデータ構造】線形検索と二分検索

検索の世界へようこそ、様々なデータ構造を学び終えた後、ようやくここまで来て、皆さんはどんな感想を持っていますか?どうせ私は勉強しながら忘れてしまったので、今図のいくつかのアルゴリズムがまだ輪をかぶっている状態なのかを話してみましょう.しかし、勉強は、一歩一歩で、しばらく分からないものを置いてもいいです.土鍋を破ることとたゆまぬ努力はもちろん良い品格ですが、本当に消化するのに時間がかかるものもあるかもしれません.実際のプロジェクトの経験が必要かもしれません.私达のプログラミング业界にとって典型的なこのような実践の学习の形式の効果はもっと良くて、多くの人は大学に行く时データの构造とその他の専门の授业に対してすべて死记の硬背を主として、何年のクラスの学友を含んですべて业务のコードの中で本当にどんなアルゴリズムを使ったことがないかもしれなくて、だからそれらを理解するのは确かにとても难しいです.この时、私达はしばらく休んで、考えを変えて、学习の最も主要なのは予习と复习で、今回の学习が终わった后で、将来更に何度も复习を行って、各种の异なる资料を研究して、遅かれ早かれある日みんなはすべて理解することができます.
今日の内容は実はとても簡単で、線形表を除いて最も簡単な内容と言える.私たちは2つの非常に初級的な検索しか研究していません.それは順序検索と半減検索です.多くの学生はとっくにできると信じています.一般の訓練機関がデータ構造とアルゴリズムを話しているとき、必ず2点を言って、順序をつけると必ず泡が立つことを言って、正規の大学の対口専門出身の学生は言うまでもありません.もちろん、この2つもとても簡単です.基礎があるかどうかにかかわらず、一緒に見てみましょう.
アルゴリズムの問題にかかわらず、実際のビジネス開発では、ソートよりも検索が重要になる可能性があります.一日中データベース向けにプログラミングして何をしているか考えてみましょう.CRUDではないでしょうか.ほとんどの業務は検索検索が多く、データベースを最適化する際にも、主に様々なクエリー文を最適化しています.もちろん、データベースの検索といえばあまりにも深いので、後でMySQLに関する知識を勉強するときに詳しく説明します.特にインデックスのB+ツリーは、データ構造とアルゴリズムの核心思想の体現です.まあ、ほらを吹かないで、ここでもっと言う勇気もありません.自分も研究していないからです.
せんけいたんさく
その名の通り、線形でも順番でも、明らかに1つのデータと1つのデータの対比でいいです.

function SearchSeq($sk, $arr)
{
    for ($i = 0; $i < count($arr); $i++) {
        if ($sk == $arr[$i]) {
            echo $i, PHP_EOL;
            break;
        }
    }
    echo "      ：" . $i, PHP_EOL;
}

うーん、本当に解釈すらしたくないので、このコードが読めないなら基本的なループや条件判断文を復習しておきましょう.一次線形ルックアップの時間的複雑さはO(N)であることは明らかである.
にぶんたんさく
こんなに簡単である以上、折り返し検索のコードを直接与えます.

function SearchBin($sk, $arr){
    $left = 0;
    $right = count($arr) - 1;
    $i = 0;
    while ($left <= $right) {
        $i++;
        $mid = (int) (($left + $right) / 2);
        if ($arr[$mid] > $sk) {
            $right = $mid - 1;
        } else if ($arr[$mid] < $sk) {
            $left = $mid + 1;
        } else {
            echo $mid, PHP_EOL;
            break;
        }
    }
    echo "      ：" . $i, PHP_EOL;
}

半角検索の前提はデータが秩序化されていることです.これにより、データの問題の長さに基づいて中間の数を取得し、比較する数と比較することができます.この数より小さい場合は、前半のデータで検索し、この数より大きい場合は、後半で検索します.例を見てから詳しく説明します.
コントラスト
2つのアルゴリズムは実は簡単で、彼らの運行状況と効率の違いを直接見てみましょう.

$arr = [5, 6, 19, 25, 4, 33, 56, 77, 82, 81, 64, 37, 91, 23];

//    56
fscanf(STDIN, "%d", $searchKey);

SearchSeq($searchKey, $arr);
// 6
//       ：6

sort($arr);
print_r($arr);

SearchBin($searchKey, $arr);
// 8
//       ：3

まず配列を定義しましたが、実際にはいくつかのデータを勝手に与えました.次にデータを入力し、配列内の位置を検索します.たとえば,テストコードに56を入力し,線形検索はループを6回行い,56の位置が下付き6の位置を見つけた.
半角検索では、配列をソートする必要があります.56は下に8と表示されていますが、半角検索のループでは、3回だけループしてこの位置を見つけました.ずいぶん速く感じたのではないでしょうか.すぐに倍になりました.これはその本当の実力ではありませんよ.半分を折って探す本当の実力は対数レベルの効率で、つまりその時間の複雑さはO(logn)です.まず、上のコードと結びつけて、この3回のループが何をしたかを見てみましょう.

が初めて入り、midは6(0+13=13、2を除く)であり、以下arr[6]と表記される値は3であり、56より小さいためleft=6+1=7

の第2サイクルは、midが10(7+13=20、2を除く)であり、以下arr[10]と表記される値は77であり、56より大きいためright=10-1=9

である

の第3ラウンドサイクル、midは9(7+9=16、2を除く)であり、以下arr[8]と表記される値は56であり、

を終了する.
実は多くの数字を当てるゲームもこのように游んでいます.例えば、あなたに1つの范囲をあげて、0-100の数をあげて、彼が書いた数を当てて、最も速くて最も簡単な方法はこのような折半検索の方法で、私たちは最大7回で100以内の数を当てることができます.明らかに、これが対数の威力です.次に、より直感的な10万個の秩序ある数を見てみましょう.最後の数を探して、順序検索と半減検索がどれだけ差があるかを見てみましょう.

$arr = range(1, 100000);
$searchKey = 100000;

SearchSeq($searchKey, $arr);
// 99999
//       ：99999

SearchBin($searchKey, $arr);
// 99999
//       ：17

やれやれ、これが対数の威力だ!!100以内の数をカバーするには2の7回が必要ですが、2の17回だけで10万以内の数をカバーすることができます.この効率の差はNが大きくなるにつれてますます明らかになります.
まとめ
今日の内容は簡単なのか,簡単なのかというと,アルゴリズムの効率に大きな違いが見られた.もちろん、折半検索にもそれ自体の限界があります.それはデータが必要な順序です.もちろん、適切な場合にはO(logn)のソートアルゴリズムを選択することもできます.これにより、全体的な時間複雑度は対数レベルに維持されます.とにかく、簡単な内容を身につけて、面接でこの関門を越えられないようにしてください.
テストコード:
https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/6.検索/source/6.1線形検索と二分検索.php
参照ドキュメント:
『データ構造』第2版、厳蔚敏
『データ構造』第2版、陳越
「データ構造ハイスコアノート」2020版、天勤大学院受験
各メディアプラットフォームで検索可能【ハードコアプロジェクトマネージャ】