432,498 Members | 1,564 Online + 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
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 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) { if (key < (vec[-1] + vec) / 2.0) return -1; } else if (key > vec) { if (key > (vec + vec) / 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. 