help-octave
[Top][All Lists]

## Re: Finding the first element that meets a condition

 From: Brett Green Subject: Re: Finding the first element that meets a condition Date: Tue, 10 Mar 2020 16:53:47 -0400

On Tue, Mar 10, 2020 at 3:34 PM Windhorn, Allen E [ACIM/LSA/MKT] <address@hidden> wrote:
Brett,

From: Help-octave <address@hidden> On Behalf Of Brett Green

> I have a sorted list of values and would like to find the index of the first
> element greater than some cutoff size. For example

> min_val = 0.3;
> arr = [.4, .8, .23, .19, .37];
> arr_sorted = sort(arr);
> index = find_first(arr_sorted,min_val);

> Is there a better way to do this than a for loop? ...

This looks like a root-finding problem, where the function whose root you
are finding is your list of sorted values, less min_val.  If the values are
distributed fairly uniformly, you could actually use a root finding routine.
Otherwise, a binary chop method would find the right value in a million
records with only 20 comparisons, much better than a linear search.

min_val =  0.30000
arr = sort(log(rand(1000000,1)+1));

function [ind, val, iter] = vsearch(arr,min_val)
iter = 0;
v1 = arr(1);
v2 = arr(end);
% Check for pathological values
if (min_val<v1)
ind = 1; % The first value is already greater than min_val
return
endif
if (min_val>v2)
ind = 0; % Error: no value in arr is greater than min_val
return
endif
arl = length(arr);
if (arl<1)
ind = 0; % Error: no values in arr
return
elsif (arl<2)
ind = 1; % Only one element, so that must be it
return
endif
ind = fix((min_val-v1)/(v2-v1)*arl); % Guess where in the pack to find the value
i1 = 1;
i2 = arl;
while (i2>i1+1)
cv = arr(ind);
if (cv<=min_val)
i1 = ind;
else
i2 = ind;
endif
ind = fix((i1+i2)/2);
iter++
endwhile
val = arr(ind);
endfunction

>> [ind, val, iter] = vsearch(arr,min_val)
ind =  349220
val =  0.30000
iter = 20

OK, this doesn't quite work -- it finds a value equal to min_val if there is one.
But you get the idea.  If you only have a few hundred items, "find" will be
better.

Regards,
Allen

Thank you to all for the suggestions! I think I will just use "find" in the end.

- Brett Green

reply via email to