How can you avoid O(N^2) cost if using unsorted array? So far there is no indication whether it would be sorted. (Addendum: I wasn't thinking so just quoted the O(N^2) cost, which really should have been O(N). Time to sleep belatedly, I suppose.)

I thought that List::MoreUtils::firstidx would use XS magic (to avoid copying). No? (I would have looked inside the C code myself but am not familiar with XS yet.)

Later ... I see now that array might be already sorted (and first element would be the interesting one).

Update: No, I guess I'm wrong. The nested loops (while and firstidx confused me).

---

  while ( -1 < ( $i = firstidx { $_ == $val } @array ) )
  {
    ...
  }
[download]

is best case O(N).
is worse case O(N²).

  for (0 .. $#array)
  {
    next if $_ != $var;
    ...
  }
[download]

is best, real & worse case O(N).

No, I was right.

  while ( -1 < ( $i = firstidx { $_ == $val } @array ) )
  {
    ...
  }
[download]

is worse case O(N²).

Take the case where the condition is true for all items.
For the first loop pass, all elements of @array are put on the stack ( time = k * N )
For the second loop pass, all remaining elements of @array are put on the stack ( time = k * (N-1) )
For the third loop pass, all remaining elements of @array are put on the stack ( time = k * (N-2) )
...
For the last loop pass, all remaining element of @array is put on the stack ( time = k * 0 )

The total time = k * ( N * (N+1) / 2 ) = O(N²)

If the language evaluated @array lazily, it would be O(N).