Search for the nearest item by bsearch?

[Davy]

For example, I have a vector:
double vector[LENGTH]={1.11,2.38,4,53,17.14...,89.12,91.34}
And if the Key I want is 5.2, the nearest item will be 4,53.

I found that if the STEP of the vector is constant,
something like {1.1,1.2,1.3,1.4,...}
the compare function will be
int compare (const void * a, const void * b)
{

if (( *(double*)a - *(double*)b )>STEP/2)
return 1;
else if (( *(double*)a - *(double*)b )<-STEP/2)
return -1;
else
return 0;
}

But if the STEP of the vector isn't constant, how to get the compare
function?

Any suggestions will be appreciated!
Best regards,
Davy

 

[Emmanuel Delahaye]

Davy wrote on 24/07/05 :

For example, I have a vector:
double vector[LENGTH]={1.11,2.38,4,53,17.14...,89.12,91.34}

I guess you wanted ... 2.38, 4.53, 17.14, ...

If not, the array is not sorted and bsearch() is not going to work.

--
Emmanuel
The C-FAQ: http://www.eskimo.com/~scs/C-faq/faq.html
The C-library: http://www.dinkumware.com/refxc.html

"C is a sharp tool"

 

[Eric Sosman]

For example, I have a vector:
double vector[LENGTH]={1.11,2.38,4,53,17.14...,89.12,91.34}
And if the Key I want is 5.2, the nearest item will be 4,53.

I found that if the STEP of the vector is constant,
something like {1.1,1.2,1.3,1.4,...}
the compare function will be
int compare (const void * a, const void * b)
{

if (( *(double*)a - *(double*)b )>STEP/2)
return 1;
else if (( *(double*)a - *(double*)b )<-STEP/2)
return -1;
else
return 0;
}

But if the STEP of the vector isn't constant, how to get the compare
function?

The bsearch() function may not be the best tool for the
job. However, I think you can use it if you are willing to
pad your vector with two extra elements, one smaller than and
one larger than any possible key:

double vector[1+LENGTH+1] = {
-DBL_MAX, 1.11,2.38,...,91.34, DBL_MAX };

Since the comparison function's second argument points to one
of the elements of vector[] and since the key (by hypothesis)
is greater than vector[0] and less than vector[1+LENGTH], there
is always a neigboring vector[] element "in the right direction."
The comparison function can take advantage of this as follows:

int compare(const void *kp, const void *vp) {
double key = *(const double*)kp;
const double *vec = (const double*)vp;
if (key < vec[0]) {
if (key < (vec[-1] + vec[0]) / 2.0)
return -1;
}
else if (key > vec[0]) {
if (key > (vec[0] + vec[1]) / 2.0)
return +1;
}
return 0;
}

Note that this approach will find 1.11 as a "match" for
a key of minus ten million; bsearch() will find the closest
value in the array, but whether it is "close enough" is your
decision.

Personally, I think I'd dispense with bsearch() and just
write a suitable binary search in-line. It seems simpler and
more straightforward to write a search for "close" than to try
to fool a search that's looking for equality.

 

[Steve Summit]

The bsearch() function may not be the best tool for the job.

Indeed. I have found it useful to implement a bsearch variant
with a slightly-wider interface which enables it to report the
bounding items -- that is, in the case where the searched-for item
isn't found, to return pointers to the one or two surrounding items.

My implementation of this was sh-callable, not C-callable (see
http://www.eskimo.com/~scs/src/#bsearch, if you're curious), but
it would be useful to define and implement a pure C-callable variant.

Steve Summit
(e-mail address removed)

 

[Davy]

Hi,

Thank you for your all help!
I have implement the method, and the search time accelerate 1000 times,
wow ;-)

All the best,
Davy