how to search an ordered array/ find bracket

Question

Alessandro D 2018-9-18

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/419618-how-to-search-an-ordered-array-find-bracket

评论： Alessandro D 2019-5-1

I am trying to write a fast procedure to locate the position of an element in a sorted array. Specifically the function should take as inputs: n*1 vector x monotonically increasing and a scalar xi, and return as output an integer j such that x(j)<= xi <x(j+1). I came up with the following:

(EX 1)

function j = mylocate1(x,xi)
n = size(x,1);
% Find x(j)<= xi <x(j+1), for j=1,..,n-1
if xi<x(1)
    j = 0;
else
    j = find(x<=xi, 1, 'last' );
end
j = max(j,1);
j = min(j,n-1);
end %close function1

or

(EX 2)

function j = mylocate2(x,xi)
n = size(x,1);
% Find x(j)<= xi <x(j+1), for j=1,..,n-1
j = sum(x<=xi);
j = max(j,1);
j = min(j,n-1);
end %close function2

I tested the above functions and they take approximately the same time but they are slow when working with large arrays. Is there anything faster? I was looking for something like the locate/hunt Fortran subroutines in the Numerical Recipes book (find location in ordered table by bisection). Is there a MEX implementation somewhere?

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Prem Kumar Tiwari 2018-9-26

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/419618-how-to-search-an-ordered-array-find-bracket#answer_338484

在 MATLAB Online 中打开

Hello Alessandro,

Since the array is sorted already, a good way to solve similar set of problems is popularly known as Binary Search. Binary Search is fastest known technique for similar problems. This runs in a time complexity of O(log(n)) and this also happens to be the fastest known technique.

You can read and learn more about it on Wiki.

As far as implementation is concerned, your implementation involves a recursion which imposes an overhead on the execution time, as well as on the memory requirements. This could be one of the reason for slow execution on large input array.

As a rule of thumb, it is considered a good practice to program in iterative fashion, this helps reduce overhead incurred due to recursive calls.

Following is an implementation of the Binary Search for use case along the lines of yours. This finds out the largest index idx, which satisfies A(idx) <= num. Since it finds out the rightmost idx the case when input array has duplicate elements is taken care of automatically. Also, if it happens that idx == length(A) then it indicates absence of A(idx+1) which is greater than num.

Feel free to customize the following implemenation as per your needs.

function idx = binarySearch(A, num)
   l = 1;
   r = length(A);
   idx = 1;
   while l < r
      idx = 1 + floor((l + r - 1) / 2);
      if A(idx) > num
        r = idx - 1; 
      elseif A(idx) <= num
        l = idx;
      end
   end
   if l == r
      idx = r; 
   end
   if A(idx) > num
     idx = -1;
   end
end

3 个评论
显示 1更早的评论隐藏 1更早的评论

Jonah Pearl 2019-5-1

在 MATLAB Online 中打开

Thank you, this helped me as well. I also modified the code to find the smallest idx such that A(idx) >= num. Though I tested for a while, I'm not 100% confident that this is correct, so if someone thinks I missed a +1 somewhere or something, a heads-up would be appreciated. Hope this helps someone else out:

% find smallest idx such that A(idx) >= num1
left = 1;
right = length(A);
idx = length(A);
while left < right
    idx = floor((left + right - 1) / 2);
    if A(idx) < num1
        left = idx + 1;
    elseif A(idx) >= num1
        right = idx;
    end
end
if left == right
    idx = right;
end
if A(idx) < num1
    idx = -1;
end