help-octave
[Top][All Lists]

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

 From: Windhorn, Allen E [ACIM/LSA/MKT] Subject: RE: Finding the first element that meets a condition Date: Tue, 10 Mar 2020 19:34:22 +0000

```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
```