Matlab search for insertion points in sorted vector

Question

How can I search for insertion points in a sorted vector?

In other words, what's the Matlab equivalent of the Octave "lookup" function: http://www.gnu.org/software/octave/doc/interpreter/Finding-Elements-and-Checking-Conditions.html#doc%2dlookup

FURTHER DESCRIPTION:

Here's what I'd like to do:

res = bsxfun(@gt, A * B, c);

Where A and B are large sparse matrices and c is a non-negative column vector.

Unfortunately, before comparing with c, the matrix A * B has too many nonzero elements to fit in memory so I can't just do this multiplication directly.

Instead I put an upper bound on the number of nonzero elements in each row by taking

counts = spones(A) * sum(spones(B),2);

Then, I want to split the counts array into n parts whose sums are roughly equal. In Octave I would say:

cs = cumsum(counts)';
sectionSize = ceil(cs(end) / n);
places = lookup(cs, (0:n) * sectionSize);
bounds = [places(1:n) + 1; places(2:(n+1))];

And now I can build res piece by piece without exhausting all the memory on the machine:

res = sparse(size(A,1),size(B,2));
for b = bounds
    res(b(1):b(2),:) = bsxfun(@gt,A(b(1):b(2),:) * B,c(b(1):b(2)));
end

I welcome any better ideas for how to do this. Especially since Matlab warns that the res array shouldn't be built by indexing in this way.

Answer 1

Octave:

octave:6> lookup([1:10], [3 7])
ans =

   3   7

Matlab:

>> find(ismember([1:10], [3 7]))

ans =

     3     7

Answer 2

I think this is just what you are looking for

 x = primes(10)
 y = 4;
 pos = find(x>y,1)-1

If you consider the vector x, and value y, you would want to insert y after point pos

Answer 3

The second output of histc should be what you're looking for. It's a full builtin, so its also pretty fast.

In analogy with octaves lookup, you can use it as:

[~, idx] = histc(y, table)

Where table is the sorted vector into which the values in y are inserted.

Answer 4

For the basic
lookup(table,y)
functionality
floor(interp1(table,val,y))
or even better
floor(interp1q(table,val,y))
could be used, where
val = (1:length(table))'.

(See help on interp1 resp. interp1q for requirements on table parameter.)
Further lookup functionality can be obtained similarly.