Continuing the discussion from A new binary-search attempt:
I was thinking of some extension from the binary search on collections that can work for sequences. Then I came up with checking if a sequence matches a given partition (with a partitioning predicate) or sort (with a comparison predicate and monotonic flag). These match the std::is_partitioned, std::is_sorted, and std::is_sorted_until functions from C++.
The code is in a gist. Sequence.partitionFailure(by:) and Sequence.sortFailure(monotonic: by:) return the two elements surrounding where a partition or sorting predicate fails. The Sequence.isPartitioned(by:) and Sequence.isSorted(monotonically: by:) are the Boolean-return variants. The sort checking methods have a flag whether consecutive elements being equal is an error or not.