SelectionSearch may fail when asking for nth number outside index range.

[ioreskovic]

Consider following example:
Asking for selectionSearch(List(5, 8, 4, 7, 3, 0, 1, 9, 6, 2), 10) should yield None, since there is no 10th element in 0-indexed list with 10 elements.

However, this call will return Some(9), which is a symptom of the bug in here:

def search(t: (List[A], A, List[A]), m: Int): Option[A] = t match {
    case (Nil, p, Nil) => Some(p)
    case (l, p, g) => select(l, p, g, l.length, m)
}

If you consider the call on singleton list with m outside range it will look like this:
search((Nil, 9, Nil), 1)

Which will return Some(9), even though m is outside the range.

The fix is to use the first pattern with guard if m == 0 and have the one without it that returns None:

def search(t: (List[A], A, List[A]), m: Int): Option[A] = t match {
    case (Nil, p, Nil) if m == 0 => Some(p)
    case (Nil, p, Nil) => None
    case (l, p, g) => select(l, p, g, l.length, m)
}

[vkostyukov]

Thanks @ioreskovic! Want to submit a PR with a fix?

[ioreskovic]

Sure thing, I'll do it tomorrow 😃