2023.12.28

C言語でのバイナリサーチとソートの実装

marugotoyoten

cs50のYoutube動画「C言語でのバイナリサーチとソートの実装」について要点と要約をまとめました

３つの要点

要点１
バイナリサーチはリニアサーチに比べて効率的で、Oの時間で動作します。
要点２
バイナリサーチは中央の要素との比較に基づいて配列の半分を破棄することで、ソートされたリスト内の高速な検索が可能です。
要点３
バイナリサーチの疑似コードでは、中央の要素を繰り返しチェックし、目的の要素が見つかるか、すべての可能性が試されるまで境界を調整します。

要約

サーチ関数の実装
このスピーチでは、helpers.cファイルでのサーチ関数とソート関数の実装方法を案内します。まずは、サーチ関数に焦点を当てる必要があります。この関数は、ヘイスタック内で値が見つかった場合にはtrueを返し、見つからなかった場合にはfalseを返します。配布コードには既にリニアサーチの実装がありますが、より効率的なバイナリサーチアルゴリズムを実装します。

バイナリサーチの理解
バイナリサーチはリニアサーチに比べて高速な代替手段ですが、リストはソートされている必要があります。リニアサーチがすべての要素を順番に調べるのに対して、バイナリサーチはOの時間で動作します。例として、サイズが9のソートされた配列で数字17を検索する場合を考えてみましょう。リニアサーチでは、数字を見つけるために7回のチェックが必要です。しかし、バイナリサーチを使用すると、まず中央の要素を調べ、値が中央より大きいか小さいかに基づいて配列の半分を破棄します。このプロセスを繰り返すことで、より速く目的の要素を見つけることができます。

バイナリサーチの疑似コード
バイナリサーチを実装するために、以下の疑似コードを使用することができます。リストの長さがゼロより大きい間、中央の要素をチェックします。もし目的の要素と一致した場合はtrueを返します。そうでなければ、境界を調整し、適切な半分の配列で検索を続けます。すべての可能性を試し尽くしても目的の要素が見つからない場合はfalseを返します。この疑似コードに従うことで、ソートされたリスト内の値を効率的に検索することができます。

結論
おめでとうございます！バイナリサーチを実装することで、ソートされたリスト内の値をリニアサーチよりもはるかに高速に検索する方法を学びました。次の部分では、C言語でのソートアルゴリズムの実装を探求します。お楽しみに！

▼今回の動画