By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
432,498 Members | 1,564 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 432,498 IT Pros & Developers. It's quick & easy.

Search for the nearest item by bsearch?

P: n/a
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

Nov 15 '05 #1
Share this Question
Share on Google+
4 Replies


P: n/a
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"
Nov 15 '05 #2

P: n/a
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

Nov 15 '05 #3

P: n/a
Eric Sosman wrote:
Davy wrote:
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.


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
sc*@eskimo.com
Nov 15 '05 #4

P: n/a
Hi,

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

All the best,
Davy

Nov 15 '05 #5

This discussion thread is closed

Replies have been disabled for this discussion.