Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Which key is closest?

Subject: Which key is closest?

From: Bruce Bowler

Date: 22 Apr, 2011 15:23:54

Message: 1 of 7

I'm having a brain fart this morning...

I have a vector of numbers which are sorted in ascending order, KEY, and
another single value, NEWKEY. NEWKEY may or may not be present in KEY. I
need to find the index in KEY whose value is the same as (easy) or the one
closest to but less than NEWKEY (where I'm stuck, short of a loop).

I seem to recall a method that uses HISTC but my pea sized brain can't
figure it out.

Any help greatly appreciated.

Thanks,
Bruce

Subject: Which key is closest?

From: alistair templeton

Date: 22 Apr, 2011 16:41:05

Message: 2 of 7


> I have a vector of numbers which are sorted in ascending order, KEY, and
> another single value, NEWKEY. NEWKEY may or may not be present in KEY. I
> need to find the index in KEY whose value is the same as (easy) or the one
> closest to but less than NEWKEY (where I'm stuck, short of a loop).

interp1 gets you close, but you can only find the closest without rounding up.

here's a non-robust, obnoxious way to play with:

key(find(diff(key>=newkey))+1)

Subject: Which key is closest?

From: Roger Stafford

Date: 22 Apr, 2011 23:05:20

Message: 3 of 7

Bruce Bowler <bbowler@bigelow.org> wrote in message <91dksaFikoU1@mid.individual.net>...
> I'm having a brain fart this morning...
>
> I have a vector of numbers which are sorted in ascending order, KEY, and
> another single value, NEWKEY. NEWKEY may or may not be present in KEY. I
> need to find the index in KEY whose value is the same as (easy) or the one
> closest to but less than NEWKEY (where I'm stuck, short of a loop).
>
> I seem to recall a method that uses HISTC but my pea sized brain can't
> figure it out.
>
> Any help greatly appreciated.
>
> Thanks,
> Bruce
- - - - - - - - -
  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.

Roger Stafford

Subject: Which key is closest?

From: ImageAnalyst

Date: 23 Apr, 2011 00:08:27

Message: 4 of 7

On Apr 22, 12:41 pm, "Alistair Templeton" <bigalt2...@yahoo.com>
wrote:
> here's a non-robust, obnoxious way to play with:
>
> key(find(diff(key>=newkey))+1)
--------------------------------------------------------------------------------------
Not sure I buy it Alistair. It's not working for me, unless I totally
misunderstood what he said. See my demo, with code that does what I
believe he said:

% Generate sample data.
key = [-1 0 1 2 3 3 4 4 6 7] % Bruce says this will be sorted
already.

% Find the index in KEY whose value is the same as
% (easy) or the one closest to but less than NEWKEY
newkey = 3.8

% There is no value the same as 3.8 in key,
% Therefore we look for the closest value
% that is less than 3.8.
% This would be a value of 3 and it occurs
% at indexes 5 and 6.

diffs = newkey - key
% Find out where the last place is that we have a value
% less than newkey.
highestIndex = find(diffs >= 0, 1, 'last') % this will find index of
6
% Find the value of key at that location.
valueThere = key(highestIndex)
% Now find any more elements that also have that value.
allMatchingIndices = find(key == valueThere)

% Alistair's solution:
AlistairSolution = key(find(diff(key>=newkey))+1)
% Hmmmm.....didn't seem to find the right
% indexes or values.

% Now try again, this time trying to find a value
% that exists in the array: 4.
% Find the index in KEY whose value is the same as
% (easy) or the one closest to but less than NEWKEY
newkey = 4

% There is a value of 4 in key,
% It occurs at indexes 7 and 8.

diffs = newkey - key
% Find out where the last place is that we have a value
% less than newkey.
highestIndex = find(diffs >= 0, 1, 'last') % this will find index of
6
% Find the value of key at that location.
valueThere = key(highestIndex)
% Now find any more elements that also have that value.
allMatchingIndices = find(key == valueThere)

% Alistair's solution:
AlistairIndexes = find(diff(key>=newkey))+1
AlistairSolution = key(find(diff(key>=newkey))+1)
% Hmmmm.....found one correctly, but didn't find
% the other one of the indexes.

Try to find the 3s:
key =
    -1 0 1 2 3 3 4 4 6 7
newkey =
    3.8000
diffs =
    4.8000 3.8000 2.8000 1.8000 0.8000 0.8000
-0.2000 -0.2000 -2.2000 -3.2000
highestIndex =
     6
valueThere =
     3
allMatchingIndices =
     5 6

AlistairSolution =
     4


Now trying to find the 4s:
newkey =
     4
diffs =
     5 4 3 2 1 1 0 0 -2 -3
highestIndex =
     8
valueThere =
     4
allMatchingIndices =
     7 8

AlistairIndexes =
     7
AlistairSolution =
     4

Subject: Which key is closest?

From: Roger Stafford

Date: 23 Apr, 2011 01:20:21

Message: 5 of 7

"Roger Stafford" wrote in message <iot1jg$5v5$1@fred.mathworks.com>...
> ........
> You will have to do one extra step to arrive at your closest location. .....
- - - - - - -
  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.)

 [~,idx] = histc(NEWKEY,[KEY,+inf]);

  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.

Roger Stafford

Subject: Which key is closest?

From: Bruce Bowler

Date: 25 Apr, 2011 13:53:37

Message: 6 of 7

On Fri, 22 Apr 2011 23:05:20 +0000, Roger Stafford set fingers to keyboard
and typed:

> Bruce Bowler <bbowler@bigelow.org> wrote in message
> <91dksaFikoU1@mid.individual.net>...
>> I'm having a brain fart this morning...
>>
>> I have a vector of numbers which are sorted in ascending order, KEY,
>> and another single value, NEWKEY. NEWKEY may or may not be present in
>> KEY. I need to find the index in KEY whose value is the same as (easy)
>> or the one closest to but less than NEWKEY (where I'm stuck, short of a
>> loop).
>>
>> I seem to recall a method that uses HISTC but my pea sized brain can't
>> figure it out.
>>
>> Any help greatly appreciated.
>>
>> Thanks,
>> Bruce
> - - - - - - - - -
> 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.
>
> Roger Stafford

Dat's da one! Thanks Roger!

Bruce

Subject: Which key is closest?

From: alistair templeton

Date: 25 Apr, 2011 14:43:05

Message: 7 of 7


> --------------------------------------------------------------------------------------
> Not sure I buy it Alistair. It's not working for me, unless I totally
> misunderstood what he said. See my demo, with code that does what I
> believe he said:

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 non-robust).

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us