バイナリサーチ（2分探索）ってのがあります。ソートされたデータから高速に値を検索できます。O(log(N))です。
Cでも標準ライブラリ的にあるし、JavaでもArraysクラスにあったりするわけです。
が、これらのバイナリサーチって同じ値がデータ中に複数あるときその中のどれが選ばれるかは保証されていないそうです。
順序（インデックス）自体に、意味がある場合、それじゃ困るという場合もあります。
横着プログラミングで取り上げられている例とか。
同じ値のものが複数ある場合は、一番最初に現れるインデックスを探して欲しいと思うわけです。
で、結局のところ、ここにあげられているbsearch_first()を使えばいいわけですが、
ソースを見ても普通のバイナリサーチとどう違うのか、一見してわからなかったり、自分で実装してみたら端点で挙動がおかしかったり、無限ループになったりとかなりはまったので、メモします。
まず、普通のバイナリサーチは次のようになります。
（検索対象配列をarray[]、検索する値をsearchValue、比較関数をcompareとし、戻り値は-1のときNotFound、それ以外のとき見つかったインデックスとします。）
foundIndex = -1;
while(low <= high) {
middle = (low + high) >> 1; /* いわゆる(low+high)/2 */
compareResult = compare(array[middle], searchValue); /* いわゆるarray[middle] - searchValue。 */
/* array[]の中身が数値ならただの引き算で。 */
if (0 == compareResult) { /* 真ん中の値が検索値と等しい */
foundIndex = middle;
break;
} else if (0 > compareResult) { /* 真ん中の値が検索値より小さい */
low = middle + 1; /* 上へ */
} else { /* 真ん中の値が検索値より大きい */
high = middle - 1; /* 下へ */
}
}
return foundIndex;で、本題の最初のインデックスを取ってくるにはどうしたらいいか。多分以下です。
/* first探索 */
foundIndex = -1;
while(low < high) { /* <=にすると無限ループ */
middle = (low + high) >> 1; /* 切り捨て。下へ移動するように。 */
compareResult = compare(array[middle], searchValue);
if (compareResult < 0) { /* 真ん中の値が検索値より小さい */
low = middle + 1;
} else if (compareResult == 0) {/* 真ん中の値が検索値と等しい */
foundIndex = middle;
high = middle; /* highがcompareResult==0であることを保証する */
} else { /* 真ん中の値が検索値より大きい */
high = middle - 1; /* 下へ */
}
}
if (foundIndex == -1 && 0 == compare(array[high], searchValue)) {
foundIndex = high;
}
return foundIndex;最終的にhighに入っている値をインデックスとして返しているわけですが、==0になってもループを抜けずにギリギリのhighを探してくるというのがミソです（多分）。
whileの判定を(low <= high)とすると、例えばlow=25、high=26、array[25]==searchvalueみたいな状況で無限ループになります。つぎで high=25となって、延々そのままです。オリジナルのバイナリサーチと違って、highの値がmiddleのままになるため、探索領域が変化しなくなります。
また、最後のifでチェックしているのは、while()の条件で=を取ったことにより、最後にhighに格納されているインデックスが調べられていない可能性があるためです。
最後のインデックスを検索するやつは、面倒なのでコードだけ。
/* last探索 */
foundIndex = -1;
while(low < high) {
middle = (low + high + 1) >> 1; /* 切り上げ。上へ移動するように。 */
compareResult = compare(array[middle], searchValue);
if (compareResult == 0) {
foundIndex = middle;
low = middle; /* lowがcompareResult==0であることを保証する */
} else if (compareResult < 0) {
low = middle + 1;
} else {
high = middle - 1;
}
}
if (foundIndex == -1 && 0 == compare(array[low], searchValue)) {
foundIndex = low;
}
return foundIndex;最初のインデックスと最後のインデックスを両方調べる必要がある場合は、横着プログラミングでやられているように、最初のインデックスを検索するときに、はじめてcomparedResult==0となったときのlowとhighを憶えておいて、最後のインデックスを調べるときはそのlowとhighからスタートすると良いです。どうせ途中まで同じことをやるのですから。
上記にあげたソースですが、プログラムから抜粋してちょっと編集しちゃったのでバグってるかも。気をつけて！（もとのプログラム自体バグってる可能性も・・・。。。）
