Re: bsearch in octave

[Geraint Paul Bevan]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

LUK ShunTim wrote:
> On 2005-06-25 1:00, Jeff Abrahamson wrote:
> 
>> I want to find the last element in a row vector that is less than a
>> given value.  I want the index of this value.  In C, for example, I'd
>> use bsearch (binary search), thus the subject on my mail.
>>
>> I don't see how to do this in octave (besides implementing binary
>> search).  Did I miss it?  Any pointers?
>>
>> Thanks much.
>>
>> For example,
>>
>>     bsearch([1, 3, 7, 15], 6)  ==> 2
>>     bsearch([1, 3, 7, 15], 7)  ==> 3
>>     bsearch([1, 3, 7, 15], 8)  ==> 3
>>
>> That is, 3 < 6 < 7, but 7 < 7 < 15 and 7 < 8 < 15.  And 3 has index 2,
>> 7 has index 3.
>>
> 
> This seems to be what you want.
> 
>>> a=[1,3,7,15];
>>> index=find(a>6)(1) - 1

That doesn't find the last matching number. If I understand the question
correctly, in the larger search space

octave> a=[1,3,7,15,4,19];

the answer should be the last number less than or equal to 6, which is 4
in position 5, but

octave> index=find(a>6)(1) - 1
index = 2


The following function works,

function i = bsearch(x,n);
  i = find(x<=n)(end);
end

octave> bsearch([1, 3, 7, 15], 6)
ans = 2
octave> bsearch([1, 3, 7, 15], 7)
ans = 3
octave> bsearch([1, 3, 7, 15], 8)
ans = 3

and for the larger search space

octave> bsearch([1,3,7,15,4,19],6)
ans = 5


- --
Geraint Bevan
http://homepage.ntlworld.com/geraint.bevan

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)
Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org

iEYEARECAAYFAkK9JX4ACgkQcXV3N50QmNPZbQCfYSPycfi444TR3aiuzR5IWiss
0PQAn2gHQU6xTEQStgMVwyMCp4uS+cY3
=tEpt
-----END PGP SIGNATURE-----



-------------------------------------------------------------
Octave is freely available under the terms of the GNU GPL.

Octave's home on the web:  http://www.octave.org
How to fund new projects:  http://www.octave.org/funding.html
Subscription information:  http://www.octave.org/archive.html
-------------------------------------------------------------