Namaran

Code daily. Without assist.

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

  1. 比較関数の結果が配列の並びと合わないときに bsearch が何を返すかを、C の規格は決めていません。missing は gcc と glibc で観測した出力で、どの行から調べるかは実装によって違います。
  2. 差を返す書き方は、値が大きいと引き算が int の範囲を超えます。値の範囲が分からない列では、(a[0] > b[0]) - (a[0] < b[0]) のように比較の結果から -1、0、1 を作ります。