http://www.mathworks.com/matlabcentral/newsreader/view_thread/306701
MATLAB Central Newsreader  Which key is closest?
Feed for thread: Which key is closest?
enus
©19942015 by MathWorks, Inc.
webmaster@mathworks.com
MATLAB Central Newsreader
http://blogs.law.harvard.edu/tech/rss
60
MathWorks
http://www.mathworks.com/images/membrane_icon.gif

Fri, 22 Apr 2011 15:23:54 +0000
Which key is closest?
http://www.mathworks.com/matlabcentral/newsreader/view_thread/306701#832544
Bruce Bowler
I'm having a brain fart this morning...<br>
<br>
I have a vector of numbers which are sorted in ascending order, KEY, and <br>
another single value, NEWKEY. NEWKEY may or may not be present in KEY. I <br>
need to find the index in KEY whose value is the same as (easy) or the one <br>
closest to but less than NEWKEY (where I'm stuck, short of a loop). <br>
<br>
I seem to recall a method that uses HISTC but my pea sized brain can't <br>
figure it out. <br>
<br>
Any help greatly appreciated.<br>
<br>
Thanks,<br>
Bruce

Fri, 22 Apr 2011 16:41:05 +0000
Re: Which key is closest?
http://www.mathworks.com/matlabcentral/newsreader/view_thread/306701#832558
alistair templeton
<br>
> I have a vector of numbers which are sorted in ascending order, KEY, and <br>
> another single value, NEWKEY. NEWKEY may or may not be present in KEY. I <br>
> need to find the index in KEY whose value is the same as (easy) or the one <br>
> closest to but less than NEWKEY (where I'm stuck, short of a loop). <br>
<br>
interp1 gets you close, but you can only find the closest without rounding up.<br>
<br>
here's a nonrobust, obnoxious way to play with:<br>
<br>
key(find(diff(key>=newkey))+1)

Fri, 22 Apr 2011 23:05:20 +0000
Re: Which key is closest?
http://www.mathworks.com/matlabcentral/newsreader/view_thread/306701#832608
Roger Stafford
Bruce Bowler <bbowler@bigelow.org> wrote in message <91dksaFikoU1@mid.individual.net>...<br>
> I'm having a brain fart this morning...<br>
> <br>
> I have a vector of numbers which are sorted in ascending order, KEY, and <br>
> another single value, NEWKEY. NEWKEY may or may not be present in KEY. I <br>
> need to find the index in KEY whose value is the same as (easy) or the one <br>
> closest to but less than NEWKEY (where I'm stuck, short of a loop). <br>
> <br>
> I seem to recall a method that uses HISTC but my pea sized brain can't <br>
> figure it out. <br>
> <br>
> Any help greatly appreciated.<br>
> <br>
> Thanks,<br>
> Bruce<br>
        <br>
Yes, by all means use 'histc' to save time searching. I believe it performs some kind of binary search. Use [inf,KEY,+inf] as the 'edges' argument and 'NEWKEY' as the single 'x' argument. It is the second returned argument you want to use to locate your position. You will have to do one extra step to arrive at your closest location. Be sure to read the documentation for it carefully.<br>
<br>
Roger Stafford

Sat, 23 Apr 2011 00:08:27 +0000
Re: Which key is closest?
http://www.mathworks.com/matlabcentral/newsreader/view_thread/306701#832613
ImageAnalyst
On Apr 22, 12:41 pm, "Alistair Templeton" <bigalt2...@yahoo.com><br>
wrote:<br>
> here's a nonrobust, obnoxious way to play with:<br>
><br>
> key(find(diff(key>=newkey))+1)<br>
<br>
Not sure I buy it Alistair. It's not working for me, unless I totally<br>
misunderstood what he said. See my demo, with code that does what I<br>
believe he said:<br>
<br>
% Generate sample data.<br>
key = [1 0 1 2 3 3 4 4 6 7] % Bruce says this will be sorted<br>
already.<br>
<br>
% Find the index in KEY whose value is the same as<br>
% (easy) or the one closest to but less than NEWKEY<br>
newkey = 3.8<br>
<br>
% There is no value the same as 3.8 in key,<br>
% Therefore we look for the closest value<br>
% that is less than 3.8.<br>
% This would be a value of 3 and it occurs<br>
% at indexes 5 and 6.<br>
<br>
diffs = newkey  key<br>
% Find out where the last place is that we have a value<br>
% less than newkey.<br>
highestIndex = find(diffs >= 0, 1, 'last') % this will find index of<br>
6<br>
% Find the value of key at that location.<br>
valueThere = key(highestIndex)<br>
% Now find any more elements that also have that value.<br>
allMatchingIndices = find(key == valueThere)<br>
<br>
% Alistair's solution:<br>
AlistairSolution = key(find(diff(key>=newkey))+1)<br>
% Hmmmm.....didn't seem to find the right<br>
% indexes or values.<br>
<br>
% Now try again, this time trying to find a value<br>
% that exists in the array: 4.<br>
% Find the index in KEY whose value is the same as<br>
% (easy) or the one closest to but less than NEWKEY<br>
newkey = 4<br>
<br>
% There is a value of 4 in key,<br>
% It occurs at indexes 7 and 8.<br>
<br>
diffs = newkey  key<br>
% Find out where the last place is that we have a value<br>
% less than newkey.<br>
highestIndex = find(diffs >= 0, 1, 'last') % this will find index of<br>
6<br>
% Find the value of key at that location.<br>
valueThere = key(highestIndex)<br>
% Now find any more elements that also have that value.<br>
allMatchingIndices = find(key == valueThere)<br>
<br>
% Alistair's solution:<br>
AlistairIndexes = find(diff(key>=newkey))+1<br>
AlistairSolution = key(find(diff(key>=newkey))+1)<br>
% Hmmmm.....found one correctly, but didn't find<br>
% the other one of the indexes.<br>
<br>
Try to find the 3s:<br>
key =<br>
1 0 1 2 3 3 4 4 6 7<br>
newkey =<br>
3.8000<br>
diffs =<br>
4.8000 3.8000 2.8000 1.8000 0.8000 0.8000<br>
0.2000 0.2000 2.2000 3.2000<br>
highestIndex =<br>
6<br>
valueThere =<br>
3<br>
allMatchingIndices =<br>
5 6<br>
<br>
AlistairSolution =<br>
4<br>
<br>
<br>
Now trying to find the 4s:<br>
newkey =<br>
4<br>
diffs =<br>
5 4 3 2 1 1 0 0 2 3<br>
highestIndex =<br>
8<br>
valueThere =<br>
4<br>
allMatchingIndices =<br>
7 8<br>
<br>
AlistairIndexes =<br>
7<br>
AlistairSolution =<br>
4

Sat, 23 Apr 2011 01:20:21 +0000
Re: Which key is closest?
http://www.mathworks.com/matlabcentral/newsreader/view_thread/306701#832617
Roger Stafford
"Roger Stafford" wrote in message <iot1jg$5v5$1@fred.mathworks.com>...<br>
> ........<br>
> You will have to do one extra step to arrive at your closest location. .....<br>
      <br>
I should have read your request more carefully. If I have understood you correctly, I think you want the following in order to use 'histc'. Assume that all elements of the sorted KEY are distinct. (We also assume here that KEY is a row vector  use "[KEY;+inf]" below for KEY a column vector.)<br>
<br>
[~,idx] = histc(NEWKEY,[KEY,+inf]);<br>
<br>
Note that if all elements of KEY are greater than NEWKEY, then 'idx' will equal zero here. This is a case you didn't cover in your requirement "closest to but less than NEWKEY" which would then be impossible to satisfy. You will have to decide how you want this case handled.<br>
<br>
Roger Stafford

Mon, 25 Apr 2011 13:53:37 +0000
Re: Which key is closest?
http://www.mathworks.com/matlabcentral/newsreader/view_thread/306701#832905
Bruce Bowler
On Fri, 22 Apr 2011 23:05:20 +0000, Roger Stafford set fingers to keyboard<br>
and typed:<br>
<br>
> Bruce Bowler <bbowler@bigelow.org> wrote in message<br>
> <91dksaFikoU1@mid.individual.net>...<br>
>> I'm having a brain fart this morning...<br>
>> <br>
>> I have a vector of numbers which are sorted in ascending order, KEY,<br>
>> and another single value, NEWKEY. NEWKEY may or may not be present in<br>
>> KEY. I need to find the index in KEY whose value is the same as (easy)<br>
>> or the one closest to but less than NEWKEY (where I'm stuck, short of a<br>
>> loop).<br>
>> <br>
>> I seem to recall a method that uses HISTC but my pea sized brain can't<br>
>> figure it out.<br>
>> <br>
>> Any help greatly appreciated.<br>
>> <br>
>> Thanks,<br>
>> Bruce<br>
>         <br>
> Yes, by all means use 'histc' to save time searching. I believe it<br>
> performs some kind of binary search. Use [inf,KEY,+inf] as the<br>
> 'edges' argument and 'NEWKEY' as the single 'x' argument. It is the<br>
> second returned argument you want to use to locate your position. You<br>
> will have to do one extra step to arrive at your closest location. Be<br>
> sure to read the documentation for it carefully.<br>
> <br>
> Roger Stafford<br>
<br>
Dat's da one! Thanks Roger!<br>
<br>
Bruce

Mon, 25 Apr 2011 14:43:05 +0000
Re: Which key is closest?
http://www.mathworks.com/matlabcentral/newsreader/view_thread/306701#832918
alistair templeton
<br>
> <br>
> Not sure I buy it Alistair. It's not working for me, unless I totally<br>
> misunderstood what he said. See my demo, with code that does what I<br>
> believe he said:<br>
<br>
Thank you for the audit! I misread and thought we would want the next largest key if it wasn't found, and I also assumed an ascending list of unique keys to search for (my code is locally famous for being nonrobust).