2つのソートされたデータのテーブルをCでバイナリ検索する方法

Question

私はC言語でバイナリ検索を使用する方法を検討しています。

私はあなたがこの2つの短い値を保持することができますショートパンツの2つの配列を持つ構造体である見ることができるように私は、構造体

struct keyval{ 
unsigned short key[2]; 
unsigned short val[2]; 
}; 

を持っている、と

を開始します。

私はこれらの構造体にメモリを割り当てます。これにより、このタイプの構造体の多くをメモリに格納することができます。

struct keyval *codes1 = malloc(sizeof(struct keyval)*(0x1000000)); 
struct keyval *codes2 = malloc(sizeof(struct keyval)*(0x1000000)); 

私はいくつかのループを通過し、struct1のkeyvalでcodes1を設定します。別のループでは、構造体keyvalでcodes2を取り込みます

このデータは反復キーに基づいて作成されます。基本的にはキー値で自動的にソートされます。

次に、データをval値でソートします。 c qsort関数 と自分自身の比較関数 を使用して、1のval配列の位置0のshortが他の構造体の同じ位置のshortよりも小さい場合は-1を返します。私はcodes2内の値に対するcodes1内のすべての値のバイナリ検索できるようにする必要があります

立ち往生していますどこ

qsort(codes1,SIZE_OF_CODES1, sizeof(struct keyval), compare); 
qsort(codes2,SIZE_OF_CODES2, sizeof(struct keyval), compare); 

int compare(const void *a, const void *b){ 
    struct keyval *ia = (struct keyval *)a; 
    struct keyval *ib = (struct keyval *)b; 

    if(ia->val[0] > ib->val[0]){ 
     return 1; 
    }else if (ia->val[0] < ib->val[0]){ 
     return -1; 
    }else{ 
     return (ia->val[1] - ib->val[1]); 
    } 

は}今これがあります。 とcodes1[i].val == codes2[i].val私はcodes1の値をプリントアウトすることができます[i]の.KEY 、その後codes2。[i]の.KEY

私の試みがあれば見つけることができません、このような

while(e <= SIZE_OF_CODES1){ 

    struct keyval *found = (struct keyval*) bsearch(&codes1[e],codes2,SIZE_OF_CODES2,sizeof(struct keyval),compare); 

    if(found){ 
     printf("\n found key = %08x %04x value = %04x %04x", found -> key, found -> key[1],found->val[0],found ->val[1]); 
    } 

    e++; 
} 

上記のコードのようになりそれは

//追加編集

---

やったドと一致したところ、コード内の場所がある私は確信しています、とデータが一致しましたバグ、そして私は、bsearchがcompare関数を呼び出すとき、それが呼び出されるたびにiaに関連するすべての値がゼロであるが、ibが正しいことを発見しました。

ソート方法が正しいか

---

誰かがバイナリ検索を実装する方法については正しい方向に私を指すことができ、私は非常に立ち往生しています

私の比較の古い機能

int compare(const void *a, const void *b){ 
struct keyval *ia = (struct keyval *)a; 
struct keyval *ib = (struct keyval *)b; 

if(ia->val[0] > ib->val[0]){ 

    return 1; 
}else if(ia->val[0] < ib->val[0]){ 
    return -1; 
}else{ 
    if(ia->val[1] > ib->val[1]){ 
     return 1; 
    }else if(ia->val[1] < ib->val[1]){ 
     return -1; 
    }else{ 
     return 0; 
     } 
} 

}

Answer 1

説明したようにリストを比較するには、thrコード1を実行した後、codes1の各エントリに対してcodes2のbsearch（）を実行します。あなたは比較を再利用することができます。私はSIZE_OF_CODES1と2が変数か定義するかどうか分からないので、各配列の要素数を反映していると仮定しています。

struct keyval *src=codes1; 
struct keyval *dest=code2; 
struct keyval *p 
int i=0; 
while(i< SIZE_OF_CODES1) 
{ 
    if((p=(struct keyval *)bsearch(src, dest, SIZE_OF_CODES2, sizeof(struct keyval), compare))!=NULL) 
     printf("duplicate codes1: %d %d codes2: %d %d\n", src->key,src->val, p->key, p->val); 
    i++ 
}