[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
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