Basic binary search in python

Question

I just started learning to code during quarantine and whilst learning python, I created this program for a binary search. This is really basic so I assume that there is a way easier method. If anyone knows how I can make this way simpler, your help would be appreciated.

list = [1,15,37,53,29,22,31,90,14,6,37,40]
finished = False
target = 37
list.sort()
print(list)
while finished == False:
    n = len(list)
    print(n)
    if target < list[int(n/2)]:
        for items in range(int(n / 2), n):
            list.pop()
        print('Item is too large.')
    elif target == list[int(n/2)]:
        finished = True
        print('The item has been found.')
    else:
        list.reverse()
        for items in range(int(n / 2), n):
            list.pop()
        list.reverse()
        print('Item is too small.')
    print(list)

Answer 1

• Avoid using list as the variable name, because it is a function in Python.
• You don't need to manipulate the list, such as list.pop() and list.reverse(). It is inefficient. You can determine the updated search range with index.
• When target is assigned a value not within list, there will be IndexError: list index out of range. It means you didn't handle the case well.

Modified code:

search_list = [1,15,37,53,29,22,31,90,14,6,37,40]
target = 37
start = 0
end = len(search_list)-1 
search_list.sort()
print('The sorted list:',search_list)
while start<=end:
    n = int((end + start)/2)
    if target < search_list[n]: # the target is small 
        end = n-1
    elif target > search_list[n]: # the target is large 
        start = n+1
    elif target == search_list[n]: # the target is found 
        print('The item {} has been found at the index {} in the sorted list.'.format(target,n))
        break 
else:
    print('The item is not found.')

Answer 2

In addition to Chris Tang's answer, I strongly suggest that you encapsulate your binary search algorithm in a function.

Currently, your code only works for the list defined at the beginning of the program. But what if you want to reuse it with another list later on? Or reuse this snippet in your next program? Encapsulating your code in a function would allow you to do that much more easily.

I understand that, as a beginner, you just wanted to see if you could implement that algorithm, and don't actually reuse it, but it is a good habit to take on early. Including docstrings to document your code to document what it does is also a good things.

Here is a slightly modified version of Chris Tang's code, encapsulating the logic:

def binary_search(search_list, target):
    """Search a sorted list for the target value
    Returns the target's index, or None if the target is not in the list"""

    start = 0
    end = len(search_list) - 1

    while start<=end:
        n = int((end + start) / 2)
        if target < search_list[n]: # the target is small 
            end = n-1
        elif target > search_list[n]: # the target is large 
            start = n+1
        else: # the target is found 
            return n
    return None


if __name__ == '__main__':
    my_list = [1,15,37,53,29,22,31,90,14,6,37,40]
    my_list.sort()
    target = 37
    target_index = binary_search(my_list, target)
    if target is not None:
        print(f'{target} was found at index {target_index}')
    else:
        print(f'{target} was not found in the list')

Some other remarks about my code:

• The function returns a value, instead of printing it. This means, should you reuse the function in some other code, you can decide what to do with the value.
• I include the execution code in a if __name__ == '__main__':. This means that, should you import your script in another piece of code, it will not run the code included in that if statement, but it will be executed if you run your script directly. You will probably never include this particular script, but I believe this is a good habit to take.
• I use f-strings instead of string.format() as it works mostly the same and I believe it is more readable. It is a matter of preference, I suppose.