Search closest value in a vector

search value in sorted vector and find index and value with respect to vector that is equal or clos

Description

Search value 'v' in sorted vector 'x' and find index and value
with respect to vector x that is equal or closest to 'v'.

If more than one value is equal then anyone can be returned
(this is property of binary search).
If more than one value is closest then first occurred is returned
(this is property of linear search).

Algorithm
First binary search is used to find v in x. If not found
then range obtained by binary search is searched linearly
to find the closest value.

INPUT:
x: vector of numeric values,
x should already be sorted in ascending order
   (e.g. 2,7,20,...120)
v: numeric value to be search in x
 
OUTPUT:
i: index of v with respect to x.
cv: value that is equal or closest to v in x

• MATLAB release: MATLAB 7.0.4 (R14SP2)

[Scott Miller]

It would be good if you flipped the i and the cv outputs around in the output vector in order to match the order used by min, max, and sort, which do related functions on vectors. This would make it easier to remember how to use the function, and introduce less cognitive dissonance when using min, max, and sort.

Scott

[James J Cai]

I would rather do:

>> z=abs(x-v);
>> [i]=find(min(z)==z)

Will your code runs fast for very long x?

[Dimitri Shvorob]

I agree with James; this submission is just redundant. Besides, (1) requiring a sorted input array is a nuisance, (2) behavior 'If more than one value is equal then anyone can be returned
(this is property of binary search).
If more than one value is closest then first occurred is returned
(this is property of linear search)' is arbitrary and, again, a nuisance.

[M Ali]

For large data size this method is extremely faster compared to using
>> z=abs(x-v);
>> [i]=find(min(z)==z).

Because it uses Binary search to for initial step. The behavior is normal because
1. Sorted input is required for binary search.
2. Binary search can return any value if more than one matches.

Many time we have to sorted the data onces but search it for millions of times e.g., Telephone directory, dictionary etc. That why binary search is preferred over linear search, even though it requires sorted input.

[Dimitri Shvorob]

Point taken; my concern is limited applicability of the code - to distinct-valued vectors, really. Btw, here's a binary-search imlementation, submitted to FEX in 2005.
http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=7552&objectType=file

[. ..]

thank you

[Schneider Huetter]

thanks!

[akash varma]

Kindly trap the case where the no. to be searched is outside the bounds. Eg:

x = [23,45,67,89,78,90]
[i,cv] = searchclosest(x,91)

gives error

?? Index exceeds matrix dimensions.

Error in ==> searchclosest at 49
y=x(to:from); %vector to be serach for closest value