Thread Subject:

Using ismember for binary search

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

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);

"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

"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..

"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

"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

"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