快速搜索排序向量中大于x的最小值 [英] Fast searching for the lowest value greater than x in a sorted vector

问题描述

快速意味着比O(N)更好，后者与find()一样好.我知道有ismembc和ismembc2，但是我不认为这两个都是我想要的.我阅读了文档，似乎他们在搜索x的成员 equal ，但我希望第一个值的索引比x大.

Fast means better than O(N), which is as good as find() is capable of. I know there is ismembc and ismembc2, but I don't think either of them are what I am looking for. I read the documentation and it seems they search for a member equal to x, but I want the index of first value greater than x.

现在，如果这两个功能 都能做到这一点，请有人举个例子，因为我不知道.

Now if either of these functions is capable of doing this, could somebody please give an example, because I can't figure it out.

理想行为:

first_greater_than([0, 3, 3, 4, 7], 1)

返回2，第一个值的索引大于1，尽管显然输入数组会大得多.

returns 2, the index of the first value greater than 1, though obviously the input array would be vastly larger.

当然，二进制搜索并不是很难实现，但是如果MATLAB已经完成了，我宁愿使用他们的方法.

Of course, a binary search isn't too difficult to implement, but if MATLAB has already done it, I would rather use their method.

推荐答案

由于输入已经排序，因此自定义二进制搜索应该可以正常工作(您可能需要对某些特殊情况进行更新，即 ie 值请求的内容少于数组的所有元素):

Since the input is already sorted a custom binary search should work (you may need to do some updates for edge cases, i.e value requested is less than all elements of the array):

function [result, res2] = binarySearchExample(val) 

    %// Generate example data and sort it
    N = 100000000;
    a = rand(N, 1);
    a = sort(a);

    %// Run the algorithm
    tic % start timing of the binary search algorithm
    div = 1;
    idx = floor(N/div);
    while(1)
        div = div * 2;

        %// Check if less than val check if the next is greater
        if a(idx) <= val,
            if a(idx + 1) > val,
                result = a(idx + 1);
                break
            else %// Get bigger 
                idx = idx + max([floor(N / div), 1]);
            end
        end
        if a(idx) > val, % get smaller
            idx = idx - floor(N / div);
        end
    end % end the while loop
    toc % end timing of the binary search algorithm

    %% ------------------------
    %% compare to MATLAB find
    tic % start timing of a matlab find
    j = find(a > val, 1);
    res2 = a(j);
    toc % end timing of a matlab find

%// Benchmark
>> [res1, res2] = binarySearchExample(0.556)

Elapsed time is 0.000093 seconds.
Elapsed time is 0.327183 seconds.

res1 =
   0.5560

res2 =
   0.5560

这篇关于快速搜索排序向量中大于x的最小值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！