Faster version of find for sorted vectors (MATLAB)

by

Here is a fast implementation using binary search. This file is also available on github

function [b,c]=findInSorted(x,range)
%findInSorted fast binary search replacement for ismember(A,B) for the
%special case where the first input argument is sorted.
%   
%   [a,b] = findInSorted(x,s) returns the range which is equal to s. 
%   r=a:b and r=find(x == s) produce the same result   
%  
%   [a,b] = findInSorted(x,[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
%
%   For any sorted list x you can replace
%   [lia] = ismember(x,from:to)
%   with
%   [a,b] = findInSorted(x,[from,to])
%   lia=a:b
%
%   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, ISMEMBER.
%
% Author Daniel Roeske <danielroeske.de>

A=range(1);
B=range(end);
a=1;
b=numel(x);
c=1;
d=numel(x);
if A<=x(1)
   b=a;
end
if B>=x(end)
    c=d;
end
while (a+1<b)
    lw=(floor((a+b)/2));
    if (x(lw)<A)
        a=lw;
    else
        b=lw;
    end
end
while (c+1<d)
    lw=(floor((c+d)/2));
    if (x(lw)<=B)
        c=lw;
    else
        d=lw;
    end
end
end

More Related Contents:

  1. Fastest sort of fixed length 6 int array
  2. C++ Sorting Algorithms [closed]
  3. Priority scoring algorithm [closed]
  4. Efficient way to add element to sorted datastructure [closed]
  5. What is stability in sorting algorithms and why is it important?
  6. Why is quicksort better than mergesort?
  7. Which sort algorithm works best on mostly sorted data? [closed]
  8. Merge Sort a Linked List
  9. Quicksort: Choosing the pivot
  10. What’s the fastest algorithm for sorting a linked list?
  11. Natural Sorting algorithm
  12. Which parallel sorting algorithm has the best average case performance?
  13. Fast algorithm implementation to sort very small list
  14. Sorting in linear time? [closed]
  15. Finding closest neighbour using optimized Levenshtein Algorithm
  16. median of three values strategy
  17. Sorting an array with minimal number of comparisons
  18. Quicksort vs heapsort
  19. Most efficient way to calculate Levenshtein distance
  20. Finding the best trade-off point on a curve
  21. Write a program to find 100 largest numbers out of an array of 1 billion numbers
  22. Quicksort superiority over Heap Sort
  23. ‘MergeSort Algorithm’ – What’s the better implementation in JAVA? [closed]
  24. Random points inside a parallelogram
  25. Can an array be grouped more efficiently than sorted?
  26. When is each sorting algorithm used? [closed]
  27. Why is bubble sort O(n^2)?
  28. Find the pair across 2 arrays with kth largest sum
  29. Find the k largest elements in order
  30. Why is the “start small” algorithm for branch displacement not optimal?

Leave a Comment