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:
Using ismember for binary search

Subject: Using ismember for binary search

From: LP

Date: 1 Aug, 2011 01:35:14

Message: 1 of 7

Hi,

i noted this Mathworks page:

http://www.mathworks.com/support/solutions/en/data/1-9NIE1N/index.html?product=ML&solution=1-9NIE1N

So I must be missing something as i'm wondering how to use ismember to do a binary search that returns the fist occurrence of an index greater than or equal to a search value, eg

a = Some sorted list of numbers (e.g. times)
val = some value to search for

x = find( a >= val,,1,'first')

Thanks, Lyle

Subject: Using ismember for binary search

From: Image Analyst

Date: 1 Aug, 2011 03:17:29

Message: 2 of 7

Lyle:
Run this demo. Perhaps all will then become clear:

a = sort(randi(100, 1, 10))
valueToLookFor = a(4)
logicalIndexes = squeeze(ismember(a, valueToLookFor))
actualIndex = find(logicalIndexes, 1, 'first')
fprintf('Found %d in "a" at index %d\n', valueToLookFor, actualIndex);

Subject: Using ismember for binary search

From: Roger Stafford

Date: 1 Aug, 2011 03:23:10

Message: 3 of 7

"LP" wrote in message <j14vsi$32l$1@newscl02ah.mathworks.com>...
> Hi,
>
> i noted this Mathworks page:
>
> http://www.mathworks.com/support/solutions/en/data/1-9NIE1N/index.html?product=ML&solution=1-9NIE1N
>
> So I must be missing something as i'm wondering how to use ismember to do a binary search that returns the fist occurrence of an index greater than or equal to a search value, eg
>
> a = Some sorted list of numbers (e.g. times)
> val = some value to search for
>
> x = find( a >= val,,1,'first')
>
> Thanks, Lyle
- - - - - - - - - -
  I don't think 'ismember' would be useful for your particular problem. On the other hand I believe 'histc' also uses a binary search technique. However, because of the form of your sought inequality you would have to transform your own quantities appropriately. Define edges = -a(end:-1:1) and use -val as the 'x' quantity. Then convert the 'bin' quantity to k = n+1-bin where n = length(a) to get the desired index relative to 'a'. (Something like that. Experiment with it until you get it right.)

  You also have to worry about the case when 'val' lies outside all intervals in 'a'. Study the documentation for 'histc'.

  By the way, using this method you can do this for 'val' a vector of values, all in one call on 'histc'.

Roger Stafford

Subject: Using ismember for binary search

From: LP

Date: 1 Aug, 2011 03:42:27

Message: 4 of 7

"Image Analyst" wrote in message <j155s9$gcr$1@newscl02ah.mathworks.com>...
> Lyle:
> Run this demo. Perhaps all will then become clear:
>
> a = sort(randi(100, 1, 10))
> valueToLookFor = a(4)
> logicalIndexes = squeeze(ismember(a, valueToLookFor))
> actualIndex = find(logicalIndexes, 1, 'first')
> fprintf('Found %d in "a" at index %d\n', valueToLookFor, actualIndex);

Hi image,
i think you'll find that solution only solves a subset of the problems defined in my example.

Ragards..

Subject: Using ismember for binary search

From: LP

Date: 1 Aug, 2011 03:55:26

Message: 5 of 7

"Roger Stafford" wrote in message <j1566u$h75$1@newscl02ah.mathworks.com>...
> "LP" wrote in message <j14vsi$32l$1@newscl02ah.mathworks.com>...
> > Hi,
> >
> > i noted this Mathworks page:
> >
> > http://www.mathworks.com/support/solutions/en/data/1-9NIE1N/index.html?product=ML&solution=1-9NIE1N
> >
> > So I must be missing something as i'm wondering how to use ismember to do a binary search that returns the fist occurrence of an index greater than or equal to a search value, eg
> >
> > a = Some sorted list of numbers (e.g. times)
> > val = some value to search for
> >
> > x = find( a >= val,,1,'first')
> >
> > Thanks, Lyle
> - - - - - - - - - -
> I don't think 'ismember' would be useful for your particular problem. On the other hand I believe 'histc' also uses a binary search technique. However, because of the form of your sought inequality you would have to transform your own quantities appropriately. Define edges = -a(end:-1:1) and use -val as the 'x' quantity. Then convert the 'bin' quantity to k = n+1-bin where n = length(a) to get the desired index relative to 'a'. (Something like that. Experiment with it until you get it right.)
>
> You also have to worry about the case when 'val' lies outside all intervals in 'a'. Study the documentation for 'histc'.
>
> By the way, using this method you can do this for 'val' a vector of values, all in one call on 'histc'.
>
> Roger Stafford

Hi Roger,

The title of that mathworks page mislead me to believing there was someway to use ismember for all logical searches! Thanks so much for confirming i'm not going crazy.

Interesting manipulation of histc and it looks mex implemented - great!

Thanks, Lyle

Subject: Using ismember for binary search

From: Image Analyst

Date: 1 Aug, 2011 11:57:25

Message: 6 of 7

"LP" wrote in message <j157b3$jms$1@newscl02ah.mathworks.com>...
> "Image Analyst" wrote in message <j155s9$gcr$1@newscl02ah.mathworks.com>...
> > Lyle:
> > Run this demo. Perhaps all will then become clear:
> >
> > a = sort(randi(100, 1, 10))
> > valueToLookFor = a(4)
> > logicalIndexes = squeeze(ismember(a, valueToLookFor))
> > actualIndex = find(logicalIndexes, 1, 'first')
> > fprintf('Found %d in "a" at index %d\n', valueToLookFor, actualIndex);
>
> Hi image,
> i think you'll find that solution only solves a subset of the problems defined in my example.
>
> Ragards..
--------------------------------------------------------
How so? Which subset is solved?
Which subset is not solved?
Image Analyst

Subject: Using ismember for binary search

From: Roger Stafford

Date: 1 Aug, 2011 15:55:14

Message: 7 of 7

"Image Analyst" wrote in message <j164b4$ine$1@newscl01ah.mathworks.com>...
> How so? Which subset is solved?
> Which subset is not solved?
> Image Analyst
- - - - - - - - -
  Hi Image Analyst. I believe that Lyle refers to the fact that his is a search for membership in the infinite continuum of an interval, a task for which 'ismember' is not qualified.

Roger Stafford

Tags for 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