7
\$\begingroup\$

New to using this platform and would like to familiarise myself with it so would just like to ask if I am exhibiting good practice with my programming.

Started the online CS50 course today and thought I would try to write my own program to execute a binary search with the small amount of programming I learnt in school, since it was mentioned within the lecture, took a little while but I figured it out.

Would just like my learning journey to be as effective as possible, so would be grateful for any improvements for efficiency within my code or point out if I have any bad habits, thanks!

import random
array = list(range(1,600))
x = random.randint(1,600)
highest = 600
length = len(array)
middle = (highest//2)
array_middle = length//2
found = False
hi = array[-1]
lo = array[0]
middle = (hi + lo)/ 2


while found == False:
    if x > hi:
        print("Your number is not in the list")
        found = True
        break
    elif x < (middle):
        array = array[:array_middle]
        highest = array[-1]
        lowest = array[0]
        middle = (highest + lowest)/2
        length = len(array)
        array_middle = length//2
        print(array)
        print(x)
    elif x > (middle):
        array = array[array_middle:]
        highest = array[-1]
        lowest = array[0]
        middle = (highest + lowest)/2
        length = len(array)
        array_middle = length//2
        print(array)
        print(x)
    else:
        print(x)
        found = True
\$\endgroup\$
2
  • \$\begingroup\$ My Python is a little rusty; does array = array[:array_middle] still create a copy of the array? You'd want to avoid that in efficient code. \$\endgroup\$ Commented Apr 19, 2022 at 16:15
  • 1
    \$\begingroup\$ If you haven't already, compare with the built-in bisect module \$\endgroup\$
    – Reinderien
    Commented Apr 19, 2022 at 16:48

1 Answer 1

9
\$\begingroup\$

Your binary search is flawed in various ways, but don't feel bad. It's a deceptively difficult algorithm to get right.

The primary problem: confusion between indexes and values. Some of your code bisects the sequence using index-based logic; other parts rely on value-based logic (taking the average of highest and lowest values). In addition to overcomplicating the implementation, that creates some bugs:

Given [1, 3] and 2.
Incorrectly says 2 is in the sequence.

Given [1, 5] and 2.
Gets stuck in an endless loop.

An edge case bug: empty sequences. Given an empty sequence, binary search should return None; your code blows up with an IndexError.

A performance problem: data copying. Your code makes copies of the input sequence. That's not needed if we stick entirely to index-based logic for bisecting.

A software engineering problem: binary search should be written as a function. Put your code in functions, even in small scripts. There are many reasons for this, and those reasons are particularly compelling when writing algorithmic code like binary search. Such a function should take the sequence and target value as input and return the target's index or None. It should not print messages to the user: leave that to a different part of the program. When you put the algorithm inside a side-effect-free function you make it much easier to test. And a problem like binary search, with its many pitfalls, requires some real testing.

Start on a good foundation: functions. We need a binary search function and a main function to exercise the code with some tests. We already have some test cases: the bugs noted above. As you write the code, try to think of the various edge cases to be explored and write a test for each one.

def main():
    TESTS = [
        ([], 2, None),
        ([1, 3], 2, None),
        ([1, 5], 2, None),
        ([1, 2, 3], 2, 1),
    ]
    for test in TESTS:
        xs, target, expected = test
        result = binary_search(xs, target)
        if result == expected:
            print('ok')
        else:
            print(f'{test} : {result}')

if __name__ == '__main__':
    main()

Binary search: do the bisecting with indexes, not values. Here's a good starting point. You can fill in the rest of the logic.

def binary_search(xs, target):
    i = 0
    j = len(xs) - 1
    while i <= j:
        mid = (i + j) // 2
        # Compare xs[mid] to the target, either returning mid
        # or modifying i and j.
        ...
    return None
\$\endgroup\$
2
  • \$\begingroup\$ Appreciate the detailed response :) - So for future reference, my function should always return a value which can then be stored in a variable outside of the local scope? Also the second line in the testing function, am I correct in assuming that the variable test is a list with 3 indexes and you are assigning values to 3 separate variables respective to each index within 1 line of code? From what I remember school never taught me anything remotely close to this - I am very much a beginner again it seems. \$\endgroup\$ Commented Apr 20, 2022 at 15:23
  • 1
    \$\begingroup\$ @LiamBolton Yes, you're on the right track: each test is a 3-element tuple and the line xs, target, expected = test "unpacks" the tuple, assigning each element to a separate variable. Regarding functions, I'm not certain I understand the intended meaning behind your precise phrasing, but setting aside terminology details, I would simply advise you to organize your programs around functions, each performing one small part of the overall job. \$\endgroup\$
    – FMc
    Commented Apr 20, 2022 at 16:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.