Davy wrote:
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.
--
Eric Sosman
es*****@acm-dot-org.invalid
