検索
ホームページよくある問題二分探索アルゴリズム

二分探索アルゴリズム

Jun 03, 2019 pm 04:12 PM
二分探索

二分探索は二分探索とも呼ばれ、より効率的な検索方法です。ただし、二分探索では、線形テーブルが逐次記憶構造を採用し、テーブル内の要素がキーワード順に配置されている必要があります。

二分探索アルゴリズム

#検索処理

まず、テーブル内の要素が昇順に並んでいると仮定して、キーを記録します。テーブルの中央 単語と検索キーワードが比較され、両者が等しい場合、検索は成功します。そうでない場合は、中央の位置のレコードを使用してテーブルが最初と最後のサブテーブルに分割されます。中間位置に記録されているサブテーブルが検索キーワードより大きい場合は前のサブテーブルをさらに検索し、そうでない場合はさらに次のサブテーブルを検索します。条件を満たすレコードが見つかって検索が成功するまで、またはサブテーブルが存在しない場合は検索が失敗するまで、上記のプロセスを繰り返します。

#比較回数

#計算式:

#配列表にキーワードが n 個ある場合:

検索が失敗した場合は、キーワードを少なくとも 1 回比較し、検索が成功した場合、キーワード比較の最大回数は b です。

注: a、b、n はすべて正の整数です。

アルゴリズムの複雑さ

二分探索の基本的な考え方は、n 個の要素をほぼ等しい 2 つの部分に分割し、a[n/2] を x と比較することです。 x=a[n/2] の場合、x が見つかり、アルゴリズムは終了します。x

時間計算量は while ループの数にすぎません。

合計 n 個の要素があり、

は n、n/2、n/4、....n/2^k と徐々に続きます (残りの要素数は次に操作されます) )、ここで、k はループの数です。

n/2^k>=1

を四捨五入すると、n/2^k=1

が得られます。 k=log2n、(基数 2、n の対数に基づく)

したがって、時間計算量は O(h)=O(log2n)

として表すことができます。以下は次のようになります。二等分 実装の疑似コードを検索します:

BinarySearch(max,min,des)

mid-while( minmid=(min max)/2

ifmid=des then

returnmid

elseifmid>des then

max=mid-1

else

min=mid 1

return max

ハーフ検索メソッドは、二分探索法 要素間の順序関係を最大限に利用し、分割統治法を採用しており、最悪の場合でも O(log n) で探索を完了することができます。その基本的な考え方は次のとおりです: (配列要素が昇順に配置されていると仮定して) n 個の要素をほぼ同じ数で 2 つの半分に分割し、a[n/2] を取得し、それを探したい x と比較します (x= の場合)。 a[n/ 2] の場合、x が見つかり、アルゴリズムは終了します。x

以上が二分探索アルゴリズムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

AI Hentai Generator

AI Hentai Generator

AIヘンタイを無料で生成します。

ホットツール

MinGW - Minimalist GNU for Windows

MinGW - Minimalist GNU for Windows

このプロジェクトは osdn.net/projects/mingw に移行中です。引き続きそこでフォローしていただけます。 MinGW: GNU Compiler Collection (GCC) のネイティブ Windows ポートであり、ネイティブ Windows アプリケーションを構築するための自由に配布可能なインポート ライブラリとヘッダー ファイルであり、C99 機能をサポートする MSVC ランタイムの拡張機能が含まれています。すべての MinGW ソフトウェアは 64 ビット Windows プラットフォームで実行できます。

SublimeText3 英語版

SublimeText3 英語版

推奨: Win バージョン、コードプロンプトをサポート!

SublimeText3 中国語版

SublimeText3 中国語版

中国語版、とても使いやすい

SAP NetWeaver Server Adapter for Eclipse

SAP NetWeaver Server Adapter for Eclipse

Eclipse を SAP NetWeaver アプリケーション サーバーと統合します。

PhpStorm Mac バージョン

PhpStorm Mac バージョン

最新(2018.2.1)のプロフェッショナル向けPHP統合開発ツール