Thanks, that looks like it will probably do the trick! But could you write a test that verifies the correct behavior?

You can do this e.g. by creating a custom class that throws an exception if it is compared to a particular value (e.g. the 3rd one in the array), and then search for something in the second half so that comparison should be skipped if the correct implementation is used. (Make sure you explode both if 3 does the comparison or if something is compared to 3, so it doesn't matter which order the algorithm does the comparison in.)

I accidentally put L/G/T/(you fill in this part) here. Not quite yet!

Ack, wrong PR. I meant the ArrayStack one.

Done, I added a test that verifies if apply is being called in the search or not (a sign of direct indexing / binary search). That does the trick, doesn't it?

@ruippeixotog - In general, no, it doesn't, because linear operations (e.g. iterator) may be implemented via apply.

Doesn't that defeat the purpose of linear search? If iterating over a collection is implemented by directly indexing elements with apply, then either apply is constant-time and the collection should be an ´IndexedSeq` instead or it isn't constant-time and binary search is actually more efficient than linear search.

Nonetheless, it doesn't seem to matter anyway. Even if testing this way may not apply to every conceivable collection, in this test I'm not using arbitrary collections - I'm using collections I created inside each test and I know the behavior of their operations. As I delegate all operations other than apply to the inner collection (either List or Vector, not abstract ones), I know that if apply is being called somewhere, it's inside search and that would prove either binary search is being used or linear search is badly implemented.

It's a little overly-specific about which elements are hit, but sure, this way is fine also. Just to be clear, though, it's not whether apply is being called at all, it's which elements are being hit, that indicates that it's binary search. (The default implementation of iterator for IndexedSeqLike uses an internal counter and apply.)

/nothingtoseehere

integrate-ide failure is unrelated to the PR

LGTM

thank you Rui!