助けが必要分割と征服アルゴリズムのための擬似コードの設計

Question

n個の整数を格納するソートされた配列Aと値キーが与えられます。 Design 配列Aで見つかった場合は、値 というキーのインデックスを返す効率的な分割と征服のアルゴリズムです。それ以外の場合、アルゴリズムは0を返します。

Answer 1

私はあなたの説明のために最良の選択はバイナリ検索二分探索法）。アルゴリズムは、配列を半分に分割し、中間にある要素が、探している項目よりも高い、低い、または等しい場合に買いに行くことです。これは、要素を対数的に検索するための検索スペースを減らすため、または要素がベクトルにないと判断するために行われます。配列は順序付けされていなければなりません。

これは私が見つからないあなたは要素のインデックスを返したい場合ので、0は最初の要素のインデックスであるならば、あなたのアルゴリズムが0を返すべきではないと思うC++

#include <vector> 



bool busqueda_dicotomica(const vector<int> &v, int principio, int fin, int &x){ 
    bool res; 
    if(principio <= fin){ 
     int m = ((fin - principio)/2) + principio; 
     if(x < v[m]) res = busqueda_dicotomica(v, principio, m-1, x); 
     else if(x > v[m]) res = busqueda_dicotomica(v, m+1, fin, x); 
     else res = true; 
    }else res = false; 
    return res; 
} 

の例であります

In this article is the detailed explanation of the binary searchまたはin this other