快速搜索排序向量中大于x的最小值

Question

快速意味着优于O(N),这与find()能够一样好.我知道有ismembc和ismembc2,但我不认为他们中有谁是我期待的.我阅读文档,似乎他们搜索的成员等于 x,但我希望第一个值的索引大于 x.

现在,如果这些功能是可以这样做的,可能有人请举一个例子,因为我无法弄清楚.

理想行为:

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

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

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

Answer 1

由于输入已经排序，自定义二分搜索应该可以工作（您可能需要对边缘情况进行一些更新，即请求的值小于数组的所有元素）：

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