Fast way to compare elements of two different sized matrices?

I need to do something like the following and am wondering if there's a faster way. mat1 is likely to be fixed size ~2000x2 or so but mat2 might get really big ~1e6?x2. So the thing only runs code if there is a pair (x,y) match between mat1 and mat2. Thoughts?

n1 = 50; n2 = 500;
mat1 = rand([n1, 2]);
mat2 = rand([n2, 2]);

for ii = 1:size(mat1, 1)
    if ismember(mat1(ii, :), mat2, 'rows')
        do my stuff
    end
end

Answer 1

[Kaustav Bhattacharya]

Assuming ismember performs linear search has worst case O(n^2) complexity. The complexity of your code would be 2(n1)*(2n2)^2 = O(n1*n2^2).

You can reshape both the matrices to 1-D arrays and sort. That would take O(n1log(n1) + n2log(n2)).

Now performing binary search in m2 for each element in m1 would take O(n1log(2n2)) and linear search on sorted arrays will take O(n1+n2). So its better to go with binary search. Total complexity O(n1log(n1) + n2log(n2) + n1log(n2))

[John Hawthorn]

Oh thats good. Thanks a bunch