bsearch.c
1.87 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/*
=============================================================================
Copyright (C) 1997-1999 NINTENDO Co.,Ltd.
$RCSfile: bsearch.c,v $
$Revision: 1.1.1.1 $
$Date: 2002/10/30 02:07:09 $
=============================================================================
関数名：bsearch
-----------------------------------------------------------------------------
書式： #include <stdlib.h>
void *bsearch(const void *key, const void *base, size_t num,
size_t width, int (*compare)(const void *, const void *));
引数： key 検索するキー
base 検索する配列のポインタ
num 検索する配列の要素数
width 検索する配列の1要素のサイズ（バイト単位）
compare ユーザーが作成した比較関数のポインタ
戻り値：検索した要素のポインタ。見つからない場合はＮＵＬＬを返す。
説明： 昇順にソートしてある配列の中からバイナリサーチで引数 keyに一致する
要素を検索する。検索する配列が昇順でなけば正しく検索できない。
引数 compareは、ユーザーが作成した比較関数のポインタ。
int compare(const void *elem1, const void *elem2);
返す値は、
0より小 elem1 は elem2より小さい
0 elem1 は elem2と等しい
0より大 elem1 は elem2より大きい
-----------------------------------------------------------------------------
*/
#include "stdlib.h"
void *bsearch(const void *key, const void *base, size_t num,
size_t width, int (*compare)(const void *, const void *))
{
char *p;
size_t i = 0, j = num -1;
size_t k;
int cmp;
do
{
k = (j + i) /2;
p = (char *)base + width*k;
cmp = compare(key,p);
if(cmp == 0)
{
while(((void *)p > base) && !compare(key,p-width))
p -= width;
return(p);
}
else if(cmp < 0)
j = k-1;
else
i = k+1;
}
while(j >= i);
return NULL;
}