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
1.1.0.0 | BSD License |
Create scripts with code, output, and formatted text in a single executable document.
Jason Baxter (view profile)
I kept finding situations where this would either crash or return the wrong value
Jason Baxter (view profile)
Greg (view profile)
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
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
thanks!
thank you
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
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.
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.
I would rather do:
>> z=abs(x-v);
>> [i]=find(min(z)==z)
Will your code runs fast for very long x?
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