Find first position satisfying condition, which is true after a certain element

Question

Can we find the first position of elements of a list satisfying a condition, with good performance, if the conditions is a tail condition of the list.

What is tail condition ? (the term is informal, personal.) I will explain with an examples.

Ex1) Let L={12,14,16,18,17,15,13} and Cond=OddQ, then Cond is a tail condition of L.
Because, the first odd number seen in the list is the 5-th element 17, any element after 17 is also odd.
For Ex1), Earliest[L,Cond] becomes 5.

Ex2) Let L={12,14,17,18,16,15,13} and Cond=OddQ, then Cond is not a tail condition of L.
Because, the first odd number seen in the list is the 3-th element 17, but there is an element that comes after 17, which is not odd. Like 18 or 16.
For Ex2), Earliest[L,Cond] becomes 6. (At present stage, you can't know why it becomes 6.)
Note that the first odd element is 3-th, not 6-th. But complaining about this is doesn't make sense, because Earliest is designed to work properly only if Cond is a tail condition of L.

Ex3) Let L={12,14,17,18,16,15,13} and Cond=#>10&, then Cond is a tail condition of L. Because every element is bigger then 10.
For Ex3), Earliest[L,Cond] becomes 1.

Ex4) Let L={12,14,17,18,16,15,13} and Cond=#>20&, then Cond is a tail condition of L. Because there is no element bigger then 20.
For Ex4), Earliest[L,Cond] becomes Missing["NotFound"].

Answer 1

Perhaps you mean binary search. If you plan to compile, see here and here.

earliest[list_,cond_] := Module[{L,R,M},
    L=0;R=Length[list]+1;While[L<R-1,M=Quotient[L+R,2];If[cond[list[[M]]],R=M,L=M];];
    If[R<=Length[list],R,Missing["NotFound"]]];

Answer 2

I've made a function called Earliest

So what is Earliest function ?

Earliest[a list_, a condition_]:=

It finds the first position of elements of a list satisfying the condition, if the condition is a tail condition of the list.
Earliest has a good performance.

What is tail condition ? (the term is informal, personal.) I will explain with an examples.

Ex1) Let L={12,14,16,18,17,15,13} and Cond=OddQ, then Cond is a tail condition of L.
Because, the first odd number seen in the list is the 5-th element 17, any element after 17 is also odd.
For Ex1), Earliest[L,Cond] becomes 5.

Ex2) Let L={12,14,17,18,16,15,13} and Cond=OddQ, then Cond is not a tail condition of L.
Because, the first odd number seen in the list is the 3-th element 17, but there is an element that comes after 17, which is not odd. Like 18 or 16.
For Ex2), Earliest[L,Cond] becomes 6. (At present stage, you can't know why it becomes 6.)
Note that the first odd element is 3-th, not 6-th. But complaining about this is doesn't make sense, because Earliest is designed to work properly only if Cond is a tail condition of L.

Ex3) Let L={12,14,17,18,16,15,13} and Cond=#>10&, then Cond is a tail condition of L. Because every element is bigger then 10.
For Ex3), Earliest[L,Cond] becomes 1.

Ex4) Let L={12,14,17,18,16,15,13} and Cond=#>20&, then Cond is a tail condition of L. Because there is no element bigger then 20.
For Ex4), Earliest[L,Cond] becomes Missing["NotFound"].

The advantage of Earliest is the speed!
Below is the code for Earliest

Earliest[L_, Cond_] := If[
  Length[L] == 0 || ! Cond[L[[-1]]],
  
  Missing["NotFound"],
  
  Module[{x = {BitLength[Length[L]] - 1}, 
    condi = (# > Length[L] || Cond[L[[#]]] &), final},
   While[x[[-1]] != 0, 
    If[condi[Total[2^x]], (x[[-1]] = x[[-1]] - 1; x), 
     x = Append[x, x[[-1]] - 1]]];
   final = 
    If[condi[Total[2^x]], x, 
     Module[{n = 1}, While[n <= Length[x] && (n - 1 == x[[-n]]), n++];
      Append[x[[;; Length[x] - (n - 1)]], n - 1]]];
   Total[2^final]]
  ]

To test Earliest, I've made a function parrot :

parrot[a_, b_] := (Earliest[Join[ConstantArray[0, a], Prime[Range[b]]], 
    PrimeQ[#] &] == If[b == 0, Missing["NotFound"], a + 1])

Now lets test :

Table[parrot[a, b], {a, 0, 10}, {b, 0, 10}]

You can check that it gives True for all cases.

To compare the performance of Earliest and method using the built-in functions, you can try :

SeedRandom[1000]; tibis = Accumulate[RandomInteger[10, 100000000]];
SelectFirst[tibis, # > 250000000 &] // Timing
Position[tibis, _?(# > 250000000 &), {1}, 1] // Timing
Earliest[tibis, # > 250000000 &] // Timing

Finally, this is a related screenshot :

Answer 3

I am probably confused, but I can't explain the following. Here is a list of 100 integers.

rr = RandomInteger[1000, 100]

(* {235,40,513,519,487,552,7,634,608,527,458,695,70,54,557,665,801,\
205,18,99,235,908,615,268,391,228,124,301,257,743,321,910,415,793,217,\
660,81,81,465,278,192,128,148,1,37,327,836,485,379,988,661,942,142,\
778,704,897,629,777,693,4,474,540,602,584,36,82,979,511,287,312,565,\
65,845,650,448,235,823,323,518,257,463,423,623,608,946,894,823,87,186,\
543,705,482,591,214,892,830,749,848,590,612} *)

If my condition is integer > 500:

Earliest[rr, # > 500 &]

(* 3 *)

It seems to me that the answer should be 95, the position of value 892, if I undertsand what Earliest is supposed to do. For example, the following code returns 95 (it also returns 0 if there is no match).

i = 0; l = Length[rr];
While[i < l, If[rr[[l - i]] > 500, i++; Continue[], Break[]]];
If[i == 0, 0, l - i + 1]