1

リストの要素の検索機能を実装し、見つかった要素のインデックスをバイナリ検索で返します。私の好奇心は、リスト内の要素のすべての出現を出力できる二分探索の方法を持つことです。

以下はコードです

int Binary_Search(int *array, int chave , int N) {
    int inf = 0; 
    int sup = N-1; 
    int meio;
    while (inf <= sup) {
        meio = inf + (sup-inf)/2;
        if (chave == array[meio])
            return meio;
        else if (chave < array[meio])
            sup = meio-1;
        else
            inf = meio+1;
    }

    return -1;   
}

他のソースの一部

このコード スニペットで重複した箇所のみを印刷するにはどうすればよいですか?

else {
    Imprime_Struct(Tabinvertida_Fornecedor[aux]->info);
    aux=aux+1;
    while (aux != i) {
        if (strcmp(chave, TabName[aux]->info.name)==0)
            Print_Struct(TabName[aux]->info);
        aux++;
    }
}
4

3 に答える 3

1

二分探索は次の 2 つの方法で実装できます。

1) so that it finds the first element not smaller than given
2) so that it finds the last element not greater than given

これら 2 つの実装を組み合わせて使用​​すると、各要素のコピー数を簡単に判断できます。

配列に整数のみが含まれている場合は、両方を使用する必要はありません。どちらかを選択して検索するだけです

1) n and n+1
2) n-1 and n

それぞれ。

これにより、対数の複雑さが得られます。

于 2013-11-10T15:25:07.587 に答える