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