Binary search in Matlab

[ghiotto86]

HI all.

I would want to know if exist a function that make this search or
exist a way to make this without loop.

thanks all.
bye

[John D'Errico]

In article <ef1dd...@webx.raydaftYaTP>,
ghiotto86 <ghio...@hotmail.com> wrote:

> I would want to know if exist a function that make this search or
> exist a way to make this without loop.

Since a binary search is inherently an iterative
process, doing so without a loop would seem to be
near heresy.

You might consider fzero, unless this really is a
homework problem. Its not truly a binary search
routine, but why should you care unless it really
is for homework?

HTH,
John D'Errico

--
The best material model of a cat is another, or preferably the same, cat.
A. Rosenblueth, Philosophy of Science, 1945

Those who can't laugh at themselves leave the job to others.
Anonymous

[ghiotto86]

you're right...
and i think that its heresy how you said :D

so exist a matlab function that make this search??

[John D'Errico]

In article <ef1d...@webx.raydaftYaTP>,
ghiotto86 <ghio...@hotmail.com> wrote:

I'm thankful that Matlab heretics need not fear
burning at the stake. There are many days my toes
would be quite toasted. All I need fear on usenet
are virtual flames. :-)

There is no explicit binary search code, but fzero
is a 1-d rootfinding code that uses a more efficient
bracketed search than a binary search when the
function is smooth. It can revert to a binary search
when it detects a problem, so it may still be
reasonable. If you truly need a binary search though,
perhaps because your problem is known to be non-smooth,
or otherwise nasty, you will need to code it yourself.

John

[ghiotto86]

pratically i make this:

implement a function that make the natural cubic spline.
the prototype is s=d_spline(x,y,t) as spline's matlab function.
now , vector x specifies the points at which the data y is given.
s is the spline point evalutate in the interval t.
in the algorithm i make the binary search for find the interval of
each elements' t in the vector x.

this is that i do :D

are you understand??

[John D'Errico]

In article <ef1d...@webx.raydaftYaTP>,
ghiotto86 <ghio...@hotmail.com> wrote:

Oh. Thats even easier. Look at histc. Specifically,
check out the second argument of histc. This does
exactly what you want.

On an earlier version of matlab (prior to version 5.3
I think) you may want bindex from the file exchange.
It solves this problem using a variety of methods,
depending upon the problem.

HTH,

[ghiotto86]

how precisily???

if i have the vector x and the vector t (valutation interval),
how to know which the interval??

for example

x= [-1 1 2 4 6];
t= -1:6

t=

-1 0 1 2 3 4 5 6

now -1 is in the 1st interval, 0 is in the always in the 1st
interval; 1 is in the 2nd interval etc etc.

how??

[John D'Errico]

In article <ef1d...@webx.raydaftYaTP>,
ghiotto86 <ghio...@hotmail.com> wrote:

For your example, look at the second argument.

[junk,bin] = histc(t,x);

bin =
1 1 2 3 3 4 4 5

-1 and 0 are in the first bin.

1 is in the second, 4 and 5 are in the 4th interval.

6 is at the very top end. (In my code bindex, I
recognized that 6 was also in the 4th interval,
which for purposes of spline interpolation, it
should be. In fact, I allowed the user to set a
flag that would do so.)

[ghiotto86]

John D'Errico wrote:

>
> [junk,bin] = histc(t,x);
>
> bin =
> 1 1 2 3 3 4 4 5
>
> -1 and 0 are in the first bin.
>
> 1 is in the second, 4 and 5 are in the 4th interval.
>
> 6 is at the very top end. (In my code bindex, I
> recognized that 6 was also in the 4th interval,
> which for purposes of spline interpolation, it
> should be. In fact, I allowed the user to set a
> flag that would do so.)
>
> John
>
>
> --
> The best material model of a cat is another, or preferably the
> same, cat.
> A. Rosenblueth, Philosophy of Science, 1945
>
> Those who can't laugh at themselves leave the job to others.
> Anonymous
>

yeah, thank you so much.
i don't read other metod of use :D

however, the last elements must be always in the 4th interval.
how do it??
simplely bin(length(bin))=bin(length(bin))-1???

[John D'Errico]

In article <ef1d...@webx.raydaftYaTP>,
ghiotto86 <ghio...@hotmail.com> wrote:

> yeah, thank you so much.
> i don't read other metod of use :D
>
> however, the last elements must be always in the 4th interval.
> how do it??
> simplely bin(length(bin))=bin(length(bin))-1???

If breaks is the vector of breakpoints, then
I usually use something like

bin(bin==length(breaks)) = length(breaks) - 1;

[ghiotto86]

thanks again you're a friend.

last question.
this method its better than search binary: the complexity spaces
them and temporal is better than binary search??

thanks

[John D'Errico]

Histc is compiled code, so I cannot say positively.
But I remember reading (on this group?) that histc
actually does a binary search under the hood. So it
should have exactly the performance characteristics
that you are looking for, but also be faster than a
matlab coded binary search.

[Steve Amphlett]

John D'Errico wrote:
>
>
> Histc is compiled code, so I cannot say positively.
> But I remember reading (on this group?) that histc
> actually does a binary search under the hood. So it
> should have exactly the performance characteristics
> that you are looking for, but also be faster than a
> matlab coded binary search.

Yep, twas I. The source code is included in the distribution.
However, the OP has also been asking the same question on <http://www.eng-tips.com>
let's face it, it's homework.

Steve (a.k.a. SomptingGuy)

[us]

John D'Errico:
<SNIP orig problem...

> Histc is compiled code, so I cannot say positively...

just a note: in the r14.sp3 distribution you'll find the c-code in

type toolbox/matlab/datafun/histc.c

us

[ghiotto86]

after all if I make therefore:

[code]

s=zeros(1,n_t);
for i=1:n_t

pos = -1;
p=1;
u=n-1;
% ricerca dell'intervallo di valutazione
while (p<=u && pos==-1)
half=round((p+u)/2);
if (x(half)==t(i))
pos=half;
else
if (x(half)<t(i))
p=half+1;
else
u=half-1;
end
end
end
if (pos==-1)
pos=u;
end

%
s(i)=d(pos)+c(pos)*(t(i)-x(pos))+(b(pos)*(t(i)-x(pos))^2)+(a(pos)*(t(i
)-x(pos))^3);

% applico Horner
point= t(i)-x(pos);
s(i)=d(pos)+point*(c(pos)+point*(b(pos)+point*a(pos)));

end
[/code]

is better than use histc????
i think no.

[ghiotto86]

my simple binary search, is better than histc???

[ghiotto86]

why you cannot say positively???

[John D'Errico]

In article <ef1dd...@webx.raydaftYaTP>,
ghiotto86 <ghio...@hotmail.com> wrote:

I don't read compiled code. I don't even read
uncompiled c-code. I hear that doing so causes
cancer in laboratory rats. (Proof: every lab
rat who ever read c-code subsequently died of
cancer. There may have been some rats who
scanned some code, not knowing how to read,
and they may have survived. This was poor
experimental design, as all rats should have
been given a reading test in advance.)

[ghiotto86]

John D'Errico wrote:
>
>

> I don't read compiled code. I don't even read
> uncompiled c-code. I hear that doing so causes
> cancer in laboratory rats. (Proof: every lab
> rat who ever read c-code subsequently died of
> cancer. There may have been some rats who
> scanned some code, not knowing how to read,
> and they may have survived. This was poor
> experimental design, as all rats should have
> been given a reading test in advance.)
>
> John
>
>
> --
> The best material model of a cat is another, or preferably the
> same, cat.
> A. Rosenblueth, Philosophy of Science, 1945
>
> Those who can't laugh at themselves leave the job to others.
> Anonymous
>

so, you advise me that my binary search is better than histc??

thank you

[Steve Amphlett]

ghiotto86 wrote:
>
>
> so, you advise me that my binary search is better than histc??

Read the code in histc.c (it's fairly straightforward binary search
code) and decide for yourself. I'd be surprised if you can improve
on it using interpreted m-file code (albeit JIT'd code).

[ghiotto86]

i have read the c-code.
pratically use the binary search :D
so its equal to my code isnt???

[us]

ghiotto86:
<SNIP perseveration beyond normal behavior...

> so its [<histc>, ed] equal to my code isnt???

well, why don't you just do this (rather than repeating this somewhat
uninteresting question over and over again)

1) take a few random inputs and look at

isequal(your_solution_output,histc_output)

2) take different inputs and look at

tic;for i=1:nr_trials; v1=your_solution(inp);end;toc
tic;for i=1:nr_trials; v2=histc(inp,...);end;toc
isequal(v1,v2)

-and (maybe)- show CSSM the results???
us

[ghiotto86]

x=[-1 2 3 6 9 10 14 17 20] ;
t=-1:0.25:20;
n_t=length(t);
n=length(x);

nr_trials=1000000;
l=n-1;lt=numel(t);

% 1st method
tic;
for i=1:nr_trials;
[ignored,index] = sort([x(1:l) t]);
index=max([find(index>l)-(1:lt);ones(1,lt)]);
end
toc

% 2nd method
tic;
for i=1:nr_trials;
[junk,bin]=histc(t,x);
if (t(n_t)==x(n))
bin(bin==n)=n-1;
end
end
toc


% 3th method
tic;
for i=1:nr_trials;
for h=1:n_t

pos(h) = -1;
p=1;
u=n-1;

while (p<=u && pos(h)==-1)
half=round((p+u)/2);
if (x(half)==t(h))
pos(h)=half;
else
if (x(half)<t(h))

p=half+1;
else
u=half-1;
end
end
end

if (pos(h)==-1)
pos(h)=u;
end
end
end
toc

isequal(bin,index,pos)

these are the results:

>> prova
Elapsed time is 55.125000 seconds.
Elapsed time is 16.063000 seconds.
Elapsed time is 55.671000 seconds.

ans =

1

>>

I am amazed of the result of the first method that is what it uses
ppval matlab function.
after all 2° the method is fastest. it's necessary to control the
complexity spaces them of every method. exists a function that it
calculates the memory allotted for every method?

[Nik Psaroudakis]

Try the matlab profiler for stats on time consumed etc.

[per isakson]

ghiotto86 wrote:
<snip>

> exists a function that it
> calculates the memory allotted for every method?

See

Title: MATLAB Monitoring Tool
Author: Joe Conti
Summary: Displays real time state of MATLAB,

in the File Exchange

/ per

[ghiotto86]

thank you