fastsearch

Search an element in the array, or the next smaller and greater

Description

Find the value (wert) in the in ascending order sorted array (array) with  
fastsearch-algorithm.  
 
function index = fastsearch (array, von, bis, wert, bias)  
 
Input  
array: array to search in  
von: lower border of the search region, should be set to 1.  
bis: higher border of the search region, should be set to  
          length(array). These variables cannot be initialize within the  
          function because of the recursion.  
wert: element to search for  
bias: 0: search exact the element  
          +1: search the element or the next greater  
          -1: search the element or the next smaller  
Output  
index: index of the element in array;  
          -1 if not found  
 
The algorithm is very quick, check the time below:  
--------------------  
>> a=rand(1,10^7);  
b=sort(a);  
tic;c=fastsearch(b,1,length(b),b(123456),1);toc  
Elapsed time is 0.000795 seconds.  
>> c  
c =  
      123456  
--------------------  
>> tic;c=fastsearch(b,1,length(b),0.16234,-1);toc  
Elapsed time is 0.014674 seconds.  
>> 0.16234-b(c)  
ans =  
  7.6316e-008  
>> 0.16234-b(c+1)  
ans =  
 -7.0494e-008

• MATLAB release: MATLAB 7.4 (R2007a)

[Yi Cao]

Excellent. Compare with  
tic,c=find(b==b(123456));toc  
Elapsed time is 0.168458 seconds.  
>>c  
c =  
123456  
---------------------------------  
tic,[dum,c]=min(abs(b-0.16234));toc  
Elapsed time is 0.487312 seconds.  
>>0.16234-b(c)  
ans =  
-6.9258e-008  
>>0.16234-b(c-1)  
ans =  
2.3127e-007  
 
It is more than 100 times faster than these normal ways to get similar answers in matlab. The weak point is that the array has to be sorted first. It will take more than 2 seconds to sort a array of size about 10^7. However, it could be useful for cases where repeated searches are required. One more thing, I guess using the golden ratio might be even more efficient.

[urs (us) schwarz]

a very nice utility; a user-friendly improvement could look like this  
1) make <fastsearch> a subroutine, eg, <fas>  
2) add a main routine, which takes care of some preprocessing, which - otherwise - may be missed by the user  
3) add a bit more help...  
 
% eg,  
function ix=fastsearch(a,v,b)  
     if ~issorted(a)  
          a=sort(a);  
     end  
          ix=fas(a,1,numel(a),v,b);  
end  
% your function <fastsearch> renamed to <fas>  
% ...  
%  
 
just a thought  
us

[urs (us) schwarz]

sorry, this was not copy/pasted properly at the end of the code example:  
 
-or- if you feel that ISSORTED eats too much time, simplify it to  
 
function ix=fastsearch(a,v,b)  
     ix=fas(a,1,numel(a),v,b);  
end  
 
which comes with no additional cost...  
 
us

[Alexander Chemeris]

It's good that such a useful algorithm in finally implemented in Matlab :)  
But this implementation have a bug. "Check if wert is inside of array." should looks like:  
 
if wert<array(von)  
    if bias==1  
        index=von;  
        return;  
    else  
        index=-1;  
        return;  
    end  
end  
if wert>array(bis)  
    if bias == -1  
        index = bis;  
        return;  
    else  
        index = -1;  
        return;  
    end  
end  
 
That is "von" and "bis" are used instead of "1" and "end". Without this fix algorthm may enter infinite recursion in certain cases.

[Valentin Kuklin]

Hi Alexander,  
 
thanks for your notes.  
 
I think there is no bug. This code with "Check if wert is inside of array." is used only for the first run, for example if you have array=1:1:100 and you search -5 or 105. For the further runs it does not play any role, the searched number will be anyway within [von, bis]. Actually it can not be infinite recursion because every "if" ends with "return" but not with the new call of function.  
 
But anyway I am happy that someone uses my function and tries to find bugs :) Thanks again :)  
 
Valentin Kuklin

[Dru Franworth]

I tried the following code and got an error message. As you can see, the number I am searching for is inside the sorted vector but it is generating an error message.  
 
-----------------------------------------------------------------------------------  
 
>> x=randn(10000,1);  
>> y=sort(x);  
>> z=randn;  
>> fastsearch(y,z,1)  
??? Error using ==> fastsearch  
Too many input arguments.  
 
Error in ==> fastsearch>fastsearch_indeed at 137  
        index=fastsearch(array,m2+1,bis,wert,bias);  
 
Error in ==> fastsearch at 59  
index = fastsearch_indeed(array,1,length(array),wert,bias);  
 
>> z  
 
z =  
 
    0.4291  
 
>> min(y)  
 
ans =  
 
   -3.5758  
 
>> max(y)  
 
ans =  
 
    4.0050  
 
>> find(abs(y-z)==min(abs(y-z)))  
 
ans =  
 
        6694

[Dru Franworth]

There is a slight bug in your code. In line 134 , you should have  
index=fastsearch_indeed(array,von,m1-1,wert,bias);  
 
Instead, you have fastsearch(array,von,m1-1,wert,bias);  
 
Same thing for line 136. Basically, all you have to do is replace fastsearch in lines 134 and 136 with fastsearch_indeed.  

[Dru Franworth]

I tried the following code in Matlab  
 
clear all  
 
x=randn(10000,1);  
 
tic  
for i=1:1000000  
y=randn;  
g=find(abs(x-y)==min(abs(x-y)));  
end  
toc  
tic  
y=sort(x);  
for i=1:1000000  
z=randn;  
qq=fastsearch(y,z,1);  
end  
toc  
----------------------------------------------------------------------------------  
 
This is the output:  
Elapsed time is 423.486252 seconds.  
Elapsed time is 357.878006 seconds.  
 
-----------------------------------------------------------------------------------  
An improvement by 15%. Pretty impressive.