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' );endj = 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-1j = 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?
Best Answer