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

问题描述

我有以下类型的code在MATLAB：

 指数=找到（[1 2 2 3 3 3 4 5 6 7 7] == 3）
 

这将返回4,5,6 - 数组等于3。现在，在元素的索引。我的code做这样的事情有很长的载体。该载体的总是排序的。

所以，我想一个功能，它取代了O（n）的复杂性找到O（log n）的的，在该阵列要排序的代价。

我知道ismember的，但我知道这不返回的所有项目，只是最后一个索引（我需​​要所有的人）。

有关可移植性的原因，我需要的解决方案是MATLAB只（不编译MEX文件等。）

解决方案

 函数[B，C] = myFind（X，范围）
％myFind在有序列表快速搜索
％[A，B] = myFind（X，s）返回其等于s的范围内。
％R = A：B和R =查找（X = = S）产生相同的结果
％
％[A，B] = myFind（A，[从，到]）返回这与和之间的范围内
％R = A：B和R =找到（X＆GT; =从与放大器，X＆LT; =到）返回相同的结果
％
％例子：
％
％X = 1:99
％S = 42
％R1 =找到（X = = S）
％[A，B] = myFind（X，S）
％R2 = A：B
％％r1和r2相等
％
％的人认为还可以找到。
％

A =范围（1）;
B =范围（结束）;
X = [ - 天道酬勤，X，INF]。
一个= 1;
B = numel（X）;
C = 1;
D = numel（X）;
而（A + 1＆LT; b || C + 1＆LT; D​​）
    LW =（地板（（A + B）/ 2））;
    如果（X（LW）＆LT; A）
        A = LW;
    其他
        B = LW;
    结束
    LW =（楼（（C + D）/ 2））;
    如果（X（LW）＆LT; = B）
        C = LW;
    其他
        D = LW;
    结束
结束
C = C-1;
b =最高（B-1,1）;
结束
 

I have code of the following kind in MATLAB:

indices = find([1 2 2 3 3 3 4 5 6 7 7] == 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.

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.

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

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

解决方案

function [b,c]=myFind(x,range)
%myFind fast search in ordered lists
%   [a,b] = myFind(x,s) returns the range which is equal to s. 
%   r=a:b and r=find(x == s) produce the same result   
%  
%   [a,b] = myFind(A,[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
%
%   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.
%

A=range(1);
B=range(end);
x=[-inf,x,inf];
a=1;
b=numel(x);
c=1;
d=numel(x);
while (a+1<b||c+1<d)
    lw=(floor((a+b)/2));
    if (x(lw)<A)
        a=lw;
    else
        b=lw;
    end
    lw=(floor((c+d)/2));
    if (x(lw)<=B)
        c=lw;
    else
        d=lw;
    end
end
c=c-1;
b=max(b-1,1);
end

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