排序向量查找的更快版本 (MATLAB) [英] Faster version of find for sorted vectors (MATLAB)

问题描述

我在 MATLAB 中有以下类型的代码:

I have code of the following kind in MATLAB:

indices = find([1 2 2 3 3 3 4 5 6 7 7] == 3)

这将返回 4,5,6 - 数组中元素的索引等于 3.现在.我的代码用很长的向量做这种事情.向量总是排序.

This returns 4,5,6 - the indices of elements in the array equal to 3. Now. my code does this sort of thing with very long vectors. The vectors are always sorted.

因此，我想要一个函数，用 O(log n) 替换 find 的 O(n) 复杂度，代价是必须对数组进行排序.

Therefore, I would like a function which replaces the O(n) complexity of find with O(log n), at the expense that the array has to be sorted.

我知道 ismember，但据我所知，它不返回所有项目的索引，只返回最后一个(我需要所有项目).

I am aware of ismember, but for what I know it does not return the indices of all items, just the last one (I need all of them).

出于可移植性的原因，我需要解决方案仅限 MATLAB(没有编译的 mex 文件等)

For reasons of portability, I need the solution to be MATLAB-only (no compiled mex files etc.)

推荐答案

这是一个使用二分查找的快速实现.此文件也可在 github

Here is a fast implementation using binary search. This file is also available on github

function [b,c]=findInSorted(x,range)
%findInSorted fast binary search replacement for ismember(A,B) for the
%special case where the first input argument is sorted.
%   
%   [a,b] = findInSorted(x,s) returns the range which is equal to s. 
%   r=a:b and r=find(x == s) produce the same result   
%  
%   [a,b] = findInSorted(x,[from,to]) returns the range which is between from and to
%   r=a:b and r=find(x >= from & x <= to) return the same result
%
%   For any sorted list x you can replace
%   [lia] = ismember(x,from:to)
%   with
%   [a,b] = findInSorted(x,[from,to])
%   lia=a:b
%
%   Examples:
%
%       x  = 1:99
%       s  = 42
%       r1 = find(x == s)
%       [a,b] = myFind(x,s)
%       r2 = a:b
%       %r1 and r2 are equal
%
%   See also FIND, ISMEMBER.
%
% Author Daniel Roeske <danielroeske.de>

A=range(1);
B=range(end);
a=1;
b=numel(x);
c=1;
d=numel(x);
if A<=x(1)
   b=a;
end
if B>=x(end)
    c=d;
end
while (a+1<b)
    lw=(floor((a+b)/2));
    if (x(lw)<A)
        a=lw;
    else
        b=lw;
    end
end
while (c+1<d)
    lw=(floor((c+d)/2));
    if (x(lw)<=B)
        c=lw;
    else
        d=lw;
    end
end
end

这篇关于排序向量查找的更快版本 (MATLAB)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！