Proposal: add quite exhaustive test case to Binary Search

Exercism Building Exercism
1

A solution to Binary Search is tricky to get right. Indeed, submissions that are faulty but still pass the tests are not uncommon.

I propose to, if possible, add a single test case to problem-specifications that exhaustively checks all indices within all arrays under a certain largish length. I expect such a test case to catch virtually all current false positives.

For examples of what such a test might look like in practice, see my drafts for Python here: Binary_Search (Python) Malfunctioning Code passes the test - #3 by MatthijsBlom

Now, I have no idea how to express this test case in problem-specifications, but it was suggested to me that I should propose this for problem-specifications anyway.

1 Like
2

Is a large length required or would, say, length of 7 be sufficient for all edge cases?

1 Like
3

I’m not that confident that 7 is enough. More so with 20. Practically certain beyond, say, 70. For noncontrived solutions, that is.

I ran the linked test drafts against both a faulty and a correct solution; the test duration cost seems negligible. ( 100 lists of lenghts 1, …, 100 make for only 5050 elements. )

4

@MatthijsBlom Do you have an example of an incorrect solution where 7 would not be enough?
And do you also want to test cases exhaustively where the (non-existing) searched-for value would be (conceptually) before the array, after it, or between elements?

5

(cc @ErikSchierboom)

6

I’m curious why you think 70 would catch something that 7 wouldn’t. I’m opposed to adding an arbitrarily large number of tests without some reasoning behind them. Ideally each test case added should have some demonstrative value, not a vague “more is better”.