いくつかのオカレンスのバイナリ検索を実行するにはどうすればよいですか？

Question

配列のバイナリ検索を実行しようとしています。すべてという文字列が出現する必要があります。私はbsearchで試しましたが、それをどうやって行うのか分かりません。

/* data structures */ 

typedef struct { 
    char *name; 
    char *value; 
} acronym; 

struct { 
    acronym *tab; 
    size_t size; 
} acronymArray; 

/* code */ 

char buf[256]; 
fgets(buf, sizeof buf, stdin); 
for (size_t i = 0; i < acronymArray.size; ++i) 
     if (!strcmp(buf, acronymArray.tab[i].name)) 
      printf("Found: %s\n", acronymArray.tab[i].value); 

/* How to translate it with a binary search ? 
    Of course my array was sorted with qsort previously */ 

私はそれを試してみたが、それは1つの出現のためにのみ機能します。

if ((k = bsearch(k, acronymArray.tab, acronymArray.size, sizeof *acronymArray.tab, compare))) 
    printf("found : %s\n", k->value); 

私は私の構造にブール変数«頭字語»について考え、私はわからないんだけど... これは宿題ではありません。

ありがとうございます！

Answer 1

それは非常に簡単でなければなりません：あなたはバイナリ検索を持つ任意の発生を見つけ、その後、あなたが見つかった項目に等しくないで何かを見つけるまで見つけ発生から前後/見る（またはあなたが見つけるまで、シーケンス終了）。すべての出現はソートされたリスト内で連続していなければなりません。

Answer 2

あなたのコードをすべて投稿するべきだと思います。文字列が格納される通常の方法は、ハッシュテーブルまたはバイナリツリーを使用する方法です。