matlab:高效搜索数组中的值

Question

我有一个已经排序的值数组(例如vec=20，54，87,233)。数组包含大约300个元素。我有一个值，我需要在这个数组中搜索它。成功的搜索不仅是精确的值，而且是范围内的+/- 5位数字。例如，在这种情况下，像17或55这样的值也应该被视为已找到。执行此操作的最有效方法是什么？我使用了下面的循环，但我猜它没有考虑到我的数组已经被排序了。此外，在非空的情况下，我可以手动检查值的距离，因为find不返回position。这不是一个大问题，因为我的“发现”只有15%。

bRes  = find(vec >= Value-5 & vec <= Value+5);
if ~isempty(bRes)
    distGap = GetGapDetails(Value, vec);
    return;
end

谢谢!瓦迪姆

Answer 1

在已经排序的列表中搜索值的最佳方法是binary search，它只需要O(log(n))时间。这比将值与列表中的每一项进行比较要好得多，这会耗费O(n)。据我所知，Matlab没有一个函数可以做到这一点。正如纳坦已经提到的，您可以(A)使用内置函数histc来完成此任务，该函数是用C语言编写的，可能会执行二进制搜索。

function good = is_within_range(value, vector, threshold)

% check that vector is sorted, comment this out for speed
assert(all(diff(vector) > 0))
assert(threshold > 0)

% pad vector with +- inf for histc
vector = [-inf, vector, inf];

% find index of value in vector, so that vector(ind) <= value < vector(ind+1)
% abuse histc, ignore bincounts
[~, ind] = histc(value, vector);

% check if we are within +- threshold from a value in vector,
% either below or above
good = (value <= vector(ind) + threshold) | value >= (vector(ind+1) - threshold);

一些快速测试：

>> is_within_range(0, [10, 30, 80], 5)
ans = 0
>> is_within_range(4, [10, 30, 80], 5)
ans = 0
>> is_within_range(5, [10, 30, 80], 5)
ans = 1
>> is_within_range(10, [10, 30, 80], 5)
ans = 1
>> is_within_range(15, [10, 30, 80], 5)
ans = 1
>> is_within_range(16, [10, 30, 80], 5)
ans = 0
>> is_within_range(31, [10, 30, 80], 5)
ans = 1
>> is_within_range(36, [10, 30, 80], 5)
ans = 0

另外，这个函数是矢量化的，因此您可以同时测试多个值：

>> is_within_range([0, 4, 5, 10, 15, 16, 31, 36], [10, 30, 80], 5)
ans =
     0     0     1     1     1     0     1     0

Answer 2

这样做的效率会更高：

bRes  = vec >= Value-5 & vec <= Value+5;
if any(bRes) ...

你是对的，MATLAB可能不会利用'vec‘已经排序的事实。您可以在感兴趣的范围内编写一个二进制搜索(即，在O(log(N))时间而不是O(N)时间内工作)，但是由于数组中只有300个元素，我怀疑您当前的实现将保持良好。

Answer 3

假设您的数组存储在变量'A‘中，值为'v'：

A(A>v+5 || A<v-5)=[];