アルゴリズム

二分探索+マスター定理



Binary Search Master Theorem



二分法：二分探索

二分探索は、データ量が多い場合に適していますが、最初にデータを並べ替える必要があります。主なアイデアは次のとおりです:(検索された配列間隔がarray [low、high]であると仮定します）

区間の中間位置K（2）を決定し、検索された値Tをarray [k]と比較します。それらが等しい場合、検索はこの位置に正常に戻ります。そうでない場合、新しい検索領域が決定され、バイナリ検索が続行されます。



面積は次のように決定されます。a.array[k]> T配列の順序から、array [k、k + 1、……、high]> Tであることがわかっているため、新しい間隔はarray [low、… …、k-1] b.array [k]

検索が中間値と比較されるたびに、検索が成功したかどうかを判断でき、失敗した場合は現在の検索間隔が半分に短縮され、再帰的な検索で十分です。時間計算量は次のとおりです。O（log2n）



1次元配列：

ハーフサーチ]数値3、12、24、36、55、68、75、88のグループがあり、指定された値24をチェックする場合。3つの変数front、mid、endは、上限、middleを指すように設定できます。および下限、mid =（フロント+エンド）/ 2。

1. front = 0（3を指す）、end = 7（88を指す）、mid = 3（36を指す）の順に開始します。



a [mid]> xなので、前半で検索する必要があります。

2.新しいend = mid-1 = 2、front = 0を変更せずに、新しいmid = 1とします。現時点ではx> a [mid]なので、必ず後半を検索してください。

3.新しいfront = mid + 1 = 2、end = 2を変更せずに、新しいmid = 2とします。この時点で、a [mid] = xで、検索は成功します。見つけたい数がシーケンス内の数ではない場合、たとえばx = 25の場合、3番目の判断が行われると、x> a [mid]は、上記の規則に従って、front = mid +1とします。は、front = 3で、front> endが表示されます。これは、検索が失敗したことを意味します。例：N個の要素の順序付けられた配列でユーザーが入力したデータxを検索します。

アルゴリズムは次のとおりです。

1.検索範囲front = 0、end = N-1を決定し、中間項mid =（front + end）/ 2を計算します。

2. a [mid] = xまたはfront> = endの場合は検索を終了し、それ以外の場合は下に進みます。

3. a [mid] xの場合、検索する要素の値は中央の要素よりも小さい範囲内にしか存在できないことを意味します。次に、mid-1の値を終了に割り当て、midを再計算して、手順に進みます。 2.2。

非再帰的な二分法

function binarySearch(arr,key){ Var low=0 //Minimum index value of array Var high=arr.length-1 //Maximum index value of array while(lowarr[mid]){ low=mid+1 }else{ high=mid-1 } } Return -1 //In the case of low>high, in this case the value of key is greater than the value of the largest element in arr or the value of key is less than the value of the smallest element in arr }

二分再帰

function binarySearch(arr,low,high,key){ if(low>high){return -1} var mid=Math.floor((low+high)/2) if(key==arr[mid]){ return mid }else if(key

二分法の時間計算量はO（logn）であり、

N *（1/2）^ x = 1

Nのスケールでは、最終的な仮説が1になるまで実行回数はxであるため、二分法の時間計算量はO（log2n）であり、底は2です。

もちろん、マスター理論を使用して二分再帰を確認することもできます

T（n）= T（n / 2）+ O（1）

二分法は次のとおりです。

{スケールnの問題を取り上げます}-> {スケールn / 2 + [いくつかの追加計算-> O（1）]の問題}

マスターの定理の公式によれば、私たちはすぐに

したがって、T（n）= O（logn）

マスター定理

マスターの定理とは何ですか？それは何のためですか？

マスターの定理は、再帰的アルゴリズムの時間計算量をすばやく取得するために使用されます。

Baidu百科事典から

以下は主な定理の内容です（このサイトの記事のスクリーンショット、忘れました）。将来、再帰的なT（n）に遭遇した場合、次のように直接、再帰の時間計算量をすばやく取得できます。

インターネット上には、a> 1は厳密ではなく、aは= 1である可能性があるという記事がたくさんあります。後者のn ^ dは、再帰の追加計算です。一般に、この計算の時間計算量はO（1）です。