bsearch(C/C++), binarySearch(Java)

[機能]

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

  Java の場合は,Arrays クラスの static メソッド binarySearch を使用します.成功するとその場所を示す 0 以上の値を返します.

[形式]
( C/C++ の場合)

	#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 より大きい

( Java の場合: Arrays クラスの static メソッド)

	int binarySearch(type[] base, type key) 
	int binarySearch(type[] base, type key)
	int binarySearch(type[] base, int from, int to, type key)
	int binarySearch(type[] base, type key, Comparator c)
	int binarySearch(type[] base, int from, int to, type key, Comparator c)
		base : ソートされた配列
		key : サーチに使用されるキー
		from, to : 探索範囲
		c : コンパレータ
			type : byte, char, int, long, double, float, object
		
[使用例]

  1. データの中から,main の引数として与えられた整数と文字列を探します(C/C++)
    #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;
    }
    
    /********************/
    /* 2つの整数の比較 */
    /********************/
    int compare_n(const void *arg1, const void *arg2)
    {
    	int *a1 = (int *)arg1;
    	int *a2 = (int *)arg2;
    	return *a1 - *a2;
    }
    
    /**********************/
    /* 2つの文字列の比較 */
    /**********************/
    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 が見つかりました
    			
  2. データの中から,main の引数として与えられた整数と文字列を探します(Java)
    import java.io.*;
    import java.util.*;
    
    public class Test {
    	public static void main (String args[]) throws ClassCastException
    	{
    		int i1, k_n, k_c, key_n, data_n [] = {10, 1, 45, 20, 0, -20, 15, 90, 5, 55};
    		String key_c, data_c[] = {"fish", "dog", "tree", "human", "cat"};
    	/*
    			 探索キー
    	*/
    		key_n = Integer.parseInt(args[0]);
    		key_c = args[1];
    	/*
    			 整数の場合
    	*/
    					// ソート前の出力
    		System.out.print("sort前   ");
    		for (i1 = 0; i1 < 10; i1++)
    			System.out.print(data_n[i1] + " ");
    		System.out.print("\n");
    					// ソートとその後の出力
    		Arrays.sort(data_n);
    		System.out.print("sort後   ");
    		for (i1 = 0; i1 < 10; i1++)
    			System.out.print(data_n[i1] + " ");
    		System.out.print("\n");
    					// 探索
    		k_n = Arrays.binarySearch(data_n, key_n);
    
    		if (k_n >= 0)
    			System.out.print("   " + data_n[k_n] + " が見つかりました\n");
    		else
    			System.out.print("   " + key_n + " は見つかりませんでした\n");
    	/*
    			 文字列の場合
    	*/
    					// ソート前の出力
    		System.out.print("sort前   ");
    		for (i1 = 0; i1 < 5; i1++)
    			System.out.print(data_c[i1] + " ");
    		System.out.print("\n");
    					// ソートとその後の出力
    		Arrays.sort(data_c);
    		System.out.print("sort後   ");
    		for (i1 = 0; i1 < 5; i1++)
    			System.out.print(data_c[i1] + " ");
    		System.out.print("\n");
    					// Comparatorを使用したソートとその後の出力(降順)
    		Comparator<String> cp = new Comp();
    		Arrays.sort(data_c, cp);
    
    		System.out.print("sort後(降順)   ");
    		for (i1 = 0; i1 < 5; i1++)
    			System.out.print(data_c[i1] + " ");
    		System.out.print("\n");
    					// 探索
    		k_c = Arrays.binarySearch(data_c, key_c, cp);
    
    		if (k_c >= 0)
    			System.out.print("   " + data_c[k_c] + " が見つかりました\n");
    		else
    			System.out.print("   " + key_c + " は見つかりませんでした\n");
    	}
    }
    
    class Comp implements Comparator <String> {
    	public int compare (String arg1, String arg2)
    	{
    		return arg2.compareTo(arg1);
    	}
    }
    			
    (出力) Java 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 
    sort後(降順)   tree human fish dog cat 
       fish が見つかりました
    			
[参照]

qsort

菅沼ホーム 本文目次 演習問題解答例 付録目次 索引