2026-11-18
find_key.c
#include <stdio.h>
#include <stdlib.h>
static int cmp(const void* p,
const void* q) {
const int *a = p, *b = q;
return a[0] - b[0] || a[1] - b[1];
}
int main(void) {
int t[][2] = {{1, 7}, {2, 3}, {2, 9}};
int k[2] = {1, 7};
int* r =
bsearch(k, t, 3, sizeof *t, cmp);
puts(r ? "found" : "missing");
}
shop と item の2列で並べた表 t から、キー k と同じ行を bsearch で探すプログラムです。表は shop の昇順で、shop が同じ行どうしは item の昇順に並んでいます。先頭の行と同じ {1, 7} を探しているので found と出るはずが、いまは missing と出ます。
Answer
Wrong
static int cmp(const void* p,
const void* q) {
const int *a = p, *b = q;
return a[0] - b[0] || a[1] - b[1];
}
C の || は、左右のどちらかが 0 でなければ 1、どちらも 0 なら 0 という int を返します。0 でない側の値そのものは返さないので、差の符号はここで失われます。cmp は等しい行に 0 を返しますが、等しくない行には、キーのほうが小さくても 1 を返します。bsearch にとって 1 は「キーはこの行より後ろにある」という意味です。
glibc の bsearch は、3行の真ん中の {2, 3} から調べます。a[0] - b[0] は 1 - 2 = -1 で 0 ではないので、cmp は 1 を返し、探索は後ろ半分の {2, 9} へ移ります。ここでも 1 が返り、調べる行がなくなって NULL が返ります。cmp が 0 を返す {1, 7} は、どの比較でも探索が後ろへ進むので一度も調べられません。1
Right
static int cmp(const void* p,
const void* q) {
const int *a = p, *b = q;
if (a[0] != b[0])
return a[0] - b[0];
return a[1] - b[1];
直した cmp は、shop が違えばその差を返し、shop が等しいときだけ item の差を返します。返す値の符号が表の並び順と一致するので、{2, 3} との比較は -1 になり、探索は前半分へ進んで {1, 7} で 0 を得ます。2列目を比べるのは1列目が等しいときだけという順序は、複合インデックスが行を並べる順序と同じです。2
- 比較関数の結果が配列の並びと合わないときに
bsearchが何を返すかを、C の規格は決めていません。missingは gcc と glibc で観測した出力で、どの行から調べるかは実装によって違います。 - 差を返す書き方は、値が大きいと引き算が
intの範囲を超えます。値の範囲が分からない列では、(a[0] > b[0]) - (a[0] < b[0])のように比較の結果から -1、0、1 を作ります。