bsearch

[機能]

　　サイズが width バイトの num 個の要素から成るソートされた配列に対し，バイナリサーチを行います．成功すると，key が最初に現れた位置を返し，失敗すると NULL を返します．

[形式]

#include <stdlib.h>

void *bsearch(const boid *key, const void *base,
              size_t num, size_t width,
              int(*compare)(const void *elm1, const void *elm2))
	key : サーチに使用されるキー
	base : ソートされた配列の先頭アドレス
	num : 配列の要素の数
	width : 各要素の大きさ（バイト単位）
	compare : 2 つの要素を比較する関数．この関数は，
		          compare(void *elm1, void *elm2)
	          の形式で与えられた 2 つの要素を比較し，配列が昇順にソートされて
	          いる場合は，次のような結果を返す必要があります．降順にソートされ
	          ているときは，正・負の関係を入れ換えます．
		          負 ： elm1 が elm2 より小さい
		          0  ： elm1 と elm2 が同じ
		          正 ： elm1 が elm2 より大きい
		

[使用例]

1. データの中から，main の引数として与えられた整数と文字列を探します

   #include <stdio.h>
   #include <stdlib.h>
   #include <string.h>
   
   int compare_n(const void *, const void *);
   int compare_c(const void *, const void *);
   
   /********/
   /* main */
   /********/
   int main(int argc, char **argv)
   {
   	int i1, key_n, *res_n, data_n[10] = {10, 1, 45, 20, 0, -20, 15, 90, 5, 55};
   	char *key_c, **res_c, *data_c[5];
   
   	for (i1 = 0; i1 < 5; i1++)
   		data_c[i1] = new char [10];
   
   	data_c[0] = "fish";
   	data_c[1] = "dog";
   	data_c[2] = "tree";
   	data_c[3] = "human";
   	data_c[4] = "cat";
   /*
   		 探索キー
   */
   	key_n = atoi(argv[1]);
   	key_c = argv[2];
   /*
   		 整数の場合
   */
   					// ソート前の出力
   	printf("sort前   ");
   	for (i1 = 0; i1 < 10; i1++)
   		printf("%d ", data_n[i1]);
   	printf("\n");
   					// ソートとその後の出力
   	qsort(data_n, 10, sizeof(int), compare_n);
   
   	printf("sort後   ");
   	for (i1 = 0; i1 < 10; i1++)
   		printf("%d ", data_n[i1]);
   	printf("\n");
   					// 探索
   	res_n = (int *)bsearch(&key_n, data_n, 10, sizeof(int), compare_n);
   
   	if (res_n != NULL)
   		printf("   %d が見つかりました\n", *res_n);
   	else
   		printf("   %d は見つかりませんでした\n", key_n);
   /*
   		 文字列の場合
   */
   					// ソート前の出力
   	printf("sort前   ");
   	for (i1 = 0; i1 < 5; i1++)
   		printf("%s ", data_c[i1]);
   	printf("\n");
   					// ソートとその後の出力
   	qsort(data_c, 5, sizeof(char *), compare_c);
   
   	printf("sort後   ");
   	for (i1 = 0; i1 < 5; i1++)
   		printf("%s ", data_c[i1]);
   	printf("\n");
   					// 探索
   	res_c = (char **)bsearch(&key_c, data_c, 5, sizeof(char *), compare_c);
   
   	if (res_c != NULL)
   		printf("   %s が見つかりました\n", *res_c);
   	else
   		printf("   %s は見つかりませんでした\n", key_c);
   
   	return 0;
   }
   
   /********************/
   /* ２つの整数の比較 */
   /********************/
   int compare_n(const void *arg1, const void *arg2)
   {
   	int *a1 = (int *)arg1;
   	int *a2 = (int *)arg2;
   	return *a1 - *a2;
   }
   
   /**********************/
   /* ２つの文字列の比較 */
   /**********************/
   int compare_c(const void *chr1, const void *chr2)
   {
   	char **c1 = (char **) chr1;
   	char **c2 = (char **) chr2;
   	return strcmp(*c1, *c2);
   }
   			

   （出力）　test 55 fish と入力した場合

   sort前   10 1 45 20 0 -20 15 90 5 55 
   sort後   -20 0 1 5 10 15 20 45 55 90 
      55 が見つかりました
   sort前   fish dog tree human cat 
   sort後   cat dog fish human tree 
      fish が見つかりました			

[参照]

qsort