0
$\begingroup$

Consider a sorted list of real numbers listz and some boolean condition condition that involves these numbers:

listz = Table[z, {z, 480., 515., 0.2}];
condition[z_(*,hidden variables_*)] = Boole[500 <= z <= 505(*&& condition on hidden variables*)];

I need to find the minimal and maximal positions of the elements of listz for which cond returns 1. I cannot use obvious operations like Position[listz, Select[listz, # >= 500 &] // Min]. The reason is that, in my real case, I do not have 1-to-1 correspondence between condition and z: it depends not only on z but also on some hidden variables; so, e.g. for some variables, the range may be narrower than the direct z-selection. I cannot simply compute the list of values of condition: it is very expensive. The only general feature I know is that the domain from listz for which condition returns 1 is connected: the list of condition values is always {0,...,0,1,...,1,0,...0}.

Because of this, I considered using binary search for this purpose. However, the code I made for this does not work:

lowest = 
 Hold@Compile[{{listz, _Real, 1}}, 
     Module[{low = 1, high = Length[listz], mid = 0, val = 0.},
      While[low < high,
       mid = Floor[(low + high)/2] // IntegerPart;
       val = condition[Compile`GetElement[listz, mid]];
       If[val == 1, high = mid, low = mid + 1];
       ];
      low
      ], CompilationTarget -> "C", RuntimeOptions -> "Speed", 
     RuntimeAttributes -> {Listable}] /. DownValues@condition // 
  ReleaseHold

This is because the desired range is in the 2nd half of listz, and my algorithm immediately goes to the wrong domain. I may manually correct it to return to the 2nd half if I would never get the unit value of condition. However, then, the range may be in the 2nd half of the 2nd half, and so on. Moreover, listz may be defined in a way such that the desired range is in the 1st half - I do not know this a priori.

Is there a proper binary algorithm allowing us to find the desired range? If not, what could be an efficient alternative?

Edit

It looks like the binary algorithm may be efficiently applied here only if I know the position of one element within the range where condition returns 1. Otherwise, I would need to iterate...

$\endgroup$
1
  • 2
    $\begingroup$ There is a binary search included in the combinatorica package. Also, there is a BinarySearchBy function in the function repository. $\endgroup$
    – Syed
    Dec 18, 2023 at 3:08

1 Answer 1

2
$\begingroup$

You may use a recursive binary search to find one position that fulfills the condition. From this you may make a binary search downwards and upwards to get the first and last position that fulfills the condition:

step[low_, high_] := Module[{pos},
   If[high - low < 2, Return[Nothing[]]]; 
   If[condition[listz[[pos = low + Round[(high - low)/2]]]] == 1, 
    Return[pos], {step[low, pos], step[pos, high]} // Flatten]
   ];
len = Length[listz];
posmin = posmax = step[1, len];
While[(tmp = step[1, posmin[[1]]]) != {}, posmin = tmp];
While[(tmp = step[posmax[[1]], len]) != {}, posmax = tmp];
{posmin[[1]], posmax[[1]]}

{101, 126}

However, note that you can use "Position" and "FirstPositio"n even if your condition does not return "1". E.g.:

FirstPosition[listz, x_ /; condition[x] == 1]

{101}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.