# Looking for a faster way of finding the first element larger than a given number in a sorted array

58 views (last 30 days)

Show older comments

Hi,

I have a vector

a = [1 1 1.01 1 1.05 1 .... 1]

which is basically all numbers >=1. I also have a vector b that is the cummulative sum of this vector (and thus sorted), so each increment in this vector is at least 1 and sometimes (often) more than 1.

I also have a random number r between 0 and the total sum of a. Now, I need to find the first element k in b that is larger than r.

I am currently using a simple find comment:

k = find(b>r, 1)

However, I feel like it should be possible for this to be faster. Since I know that k should be at least floor(r) as increments in the cumsum vector are at least 1, I have tried

n = floor(r)

k = find(b(n:end)>r, 1) + n-1

But this seems to be slower despite skipping searching the first n enties of b. Is there an build-in option in matlab for starting the search at a certain index? If not, is there any other faster way? This function takes about 65% of my total computing time. a Is a vector of size 10.000 but it changes very often and I have to make this call millions of times.

### Accepted Answer

dpb
on 3 Aug 2021

With the JIT compiler, loops are pretty quick any more...in fact, with the starting point as the beginning loop index, that may, indeed, be the fastest option. I'd use a counted loop and break though, not the while I think, although you can compare...

for k=floor(r):numel(b)

if b(k)>r, break, end

end

##### 3 Comments

dpb
on 8 Aug 2021

### More Answers (2)

Bruno Luong
on 3 Aug 2021

Edited: Bruno Luong
on 3 Aug 2021

You might try

k = discretize(r,b);

if b(k) == r

k = k+1;

end

Zhunping Xue
on 7 Oct 2022

If it's an ordered cumsum vector and about 10,000 entries in size, you probably can simply implement the binary search algorith (you can find it anywhere, say, https://en.wikipedia.org/wiki/Binary_search_algorithm). Matlab's find option is a linear search and does not take advantage of the fact that your vector is ordered. It should come out to be orders faster than what you're doing!

James Tursa had the best solution I can think of, a binary search with mex -- but you don't have to do it in mex.

My really, really primitive code (I'm a biologist, don't laugh):

function m=find_ordered_array(array, value)

% finds value in ordered array, else returns the closest value larger than

% the value sought for

% if(value<array(1) || value > array(end))

% disp('value outside array');

% m=-1;

% return;

% else

% l=1;

tol=1e-15;

h=length(array);

if(array(1)>=value)

m=1;

return;

elseif(array(h)<=value)

m=h;

return;

else

l=1;

h=length(array);

m=floor((l+h)/2);

while(l<h-1 && abs(array(m)-value)>tol)

if(array(m)>value)

h=m;

else

l=m;

end

m=floor((l+h)/2);

end

if(abs(array(m)-value)<tol)

elseif(abs(array(h)-value)<tol)

m=h;

elseif(abs(array(l)-value)<tol)

m=l;

else

m=l;

end

m=m+1;

end

% end

##### 1 Comment

### See Also

### Categories

### Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!