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

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"].

• What about FirstPosition? Jun 27 at 12:05
• What is your question? This is a Q&A site, so you should split this post in two, resulting in a question that explains the requirements you have for your function, with sample inputs and outputs, and then a self-answer showing your current implementation. Jun 27 at 12:08
• @MacroB, I understood. I'll split the post in two, thank you. Jun 27 at 12:55
• If r is the result, a way to do some level of verification after the fact about having a tail condition to begin with would be to run Earliest on part ;;r-1 and on part r;; . The result should be {Missing[Not Found],1}. Jun 27 at 21:05

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"]]];

• I verified that your earliest behaves correctly just as mine! I intended to avoid computation like addition, Quotient[#,2], for better performance. But come to think of it now, such consideration will not make notable improvement of performance. And your code is much shorter. Jun 27 at 18:21

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 :

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]

• The condition # > 500 & is NOT a tail condition of rr. In short, Earliest is meaningless in your example. If rr were any list of monotonic increasing sequence, then # > 500 & would be a tail condition of rr. Jun 27 at 17:24
• I see. So a tail condition exists if the first element matching the condition is the first element of the tail... and Earliest assumes, but does not verify, that the given condition is a tail condition. Jun 27 at 17:39
• Yes, use Earliest only when we already know the condition is a tail condition of L Jun 27 at 18:23