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.