Find last item in an indexed sequence matching a predicate

Question

What is a proper Scala way to find a last element in the indexed sequence (like Vector, Array or ArrayBuffer) matching a predicate, assuming we want the solution to be fast when the element exists near the sequence end?

One could use seq.reverse.find to achieve this, but that is O(N), as reverse makes a complete copy of the sequence.

Answer 1

I'd use .lastIndexWhere defined in IndexedSeqOptimized to get the index of the last element matching your predicate, and then a simple .apply(i) to get it.

.lastIndexWhere in IndexedSeqOptimized is defined as a decreasing loop, checking each element for p(i) from end to start.

If the element you seek is near the end of the collection this should give you good performances.
Note however that this is still O(n). If, for instance, there are not element matching your predicate, you'll end up checking every elements.

---

Example using .lastIndexWhere:

scala> val a = (1 to 100).toArray
a: Array[Int] = Array(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100)

scala> def p(i: Int) = {println(s"Checking for $i!"); i == 97}
p: (i: Int)Boolean

scala> a(a.lastIndexWhere(p))
Checking for 100!
Checking for 99!
Checking for 98!
Checking for 97!
res0: Int = 97

Answer 2

Vector.reverseIterator is O(1).

Answer 3

Starting Scala 2.13 you can use findLast, which is the reverse of find and applies the predicate to match from the end of the collection:

Array((10, 'a'), (20, 'b'), (30, 'c'), (20, 'd')).findLast(_._1 == 20)
// Option[(Int, Char)] = Some(20, 'd')