Binary_Search (Python) Malfunctioning Code passes the test


I successfully submitted my solution to binary search. However I came across a strange behaviour in my own dev environment.
Although the values 4 and 8 are contained in the list [1, 3, 4, 6, 8, 9, 11], my code raises ValueError("value not in array") only on these two values. Because these values are not tested explicitly, the code passes the test.

I tested out the values by manually changing the values and as expected, the test didn’t pass, see code.

This is the test file on GitHub
Test starts at line17

def test_finds_a_value_in_the_middle_of_an_array(self):

        self.assertEqual(find([1, 3, 4, 6, 8, 9, 11], 6), 3)
        # fails => self.assertEqual(find([1, 3, 4, 6, 8, 9, 11], 4), 2)
        # fails => self.assertEqual(find([1, 3, 4, 6, 8, 9, 11], 8), 4)

I still don’t understand, why my code behaves like that and I am not proficient enough, to help solve this issue in the testing.

For reference, here is my code, but I don’t expect it to be solved here. I just want the test to catch errors in the code

Thanks Murat

def find(search_list: list[int], value: int) -> int:
    sorted_list = sorted(search_list)

    left, right = 0, len(search_list) - 1

    if not search_list:
        raise ValueError("value not in array")
    if search_list[0] == value:
        return 0
    elif search_list[-1] == value:
        return len(search_list) - 1
    while left < right:
        mid = left + (right - left) // 2
        if sorted_list[mid] == value:
            return mid
        elif sorted_list[mid] < value:
            left = mid + 1
            right = mid - 1

    raise ValueError("value not in array")

Your current implementation is not correct because your left and right are defined so that you are searching in the closed interval [left, right] , that is both endpoints are considered valid targets, but your while loop is designed for the half-open interval [left, right), that is it stops when left == right.

You would’ve caught the error if you didn’t check for the special cases [0] and [-1] before you proceed to the while loop. A robust implementation would not need to test these special cases anyways.
I believe replacing while left < right: with while left <= right: should pass your extra tests.

Also, the input array is already sorted, no need to sort it yourself. It would defeat the purpose of the binary-search if you had to sort the input before the search.

As for updating the tests to cover as many buggy implementations as possible: Exercism is focused on the concept of mentorship, and it is the intention that students request code reviews from experienced mentors who would then work with you to make sure your implementation is correct and follows best practices.
I encourage you to request a code review for this and other exercises that you solve, especially if, like in this case, you find some issues with the implementation.


@dreig here is @muritz’ mentoring request: Exercism

@BethanyG how do you feel about a adding a test case that covers simply all lengths < 100 and all indices?

Rough examples
def test_finds_all_elements_in_all_lists_of_lengths_up_to_100(self):
    EXCEPTION_THROWN = object()

    def try_(f, *args):
        try:    return f(*args)
        except: return EXCEPTION_THROWN

    lists = (list(range(length)) for length in range(1, 100))
        all(try_(find, xs, x) == x 
            for xs in lists
            for x in xs
def test_finds_all_elements_in_all_lists_of_lengths_up_to_95(self):
    ascii_printables = string.ascii_printable[:-5]  # the last 5 aren't _nicely_ printable
    for length in range(1, len(ascii_printables)):
        characters = ascii_printables[:length]
        for c in characters:
            self.assertEqual(find(characters, c), ord(c) - space)

I would be surprised to find a buggy submission that passes such a test.

I think I’ve already said what I had to say about this implementation, perhaps someone who has more experience with python should pick up that mentoring request.

@muritz binary search is such a fundamental algorithm and there are many online platforms that have extensive test suites where you can test your implementation and be reasonably confident that it’s correct.
May I recommend the following tutorials, they come with links to sites where you can test your implementation:

1 Like

This is a practice exercise that has canonical data - the Python track pulls this data in to generate tests via a template, so proposed new test cases should be discussed and made in a problem specifications context.

That way, other tracks can “plug” this missing test cases hole as well, since the data is shared across tracks. :slightly_smiling_face:

I’d suggest a new more general thread proposing any missing test cases for Problem Specs so maintainers can discuss things and/or a PR to Problem Specifications, since this really isn’t a Python-specific issue.

1 Like

If not by accident, I wouldn’t even have caught this. I thought I might raise this issue to the attention to the more experienced community members, than I am :blush:

Anyway thank you for your explanations, meanwhile I have seen other solutions as well and will try to implement the necessary changes to my code.

I will also check the links, that you have provided, to learn more about the topic.