File Exchange

image thumbnail

Search closest value in a vector

version 1.1.0.0 (11.5 KB) by Dr. Murtaza Khan
search value in sorted vector and find index and value with respect to vector that is equal or clos

1 Download

Updated 09 Jul 2009

View License

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

Comments and Ratings (11)

I kept finding situations where this would either crash or return the wrong value

Greg

I added the following code after the line 'to=length(x);'. It fixes errors from the search value being out of bounds.

if v<=x(1)
i=1;
cv=x(1);
return
elseif v>=x(end)
i=length(x);
cv=x(end);
return
end

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

Schneider Huetter

thanks!

. ..

thank you

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

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

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.

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?

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

Updates

1.1.0.0

BSD License

MATLAB Release Compatibility
Created with R14SP2
Compatible with any release
Platform Compatibility
Windows macOS Linux