so I'm trying to learn programming myself in Python language and was confused implementing Binary Search in Python. So here's what I have done

list = [3,6,8,12,14,17,25,29,31,36,42,47,63,55,62]
key = 42
print(list)

def high(sorted_list):
    max_index = len(sorted_list)
    return max_index
    
def low(sorted_list):
    start_index = 0  
    return start_index  

def mid(sorted_list):
    mid_index = ( low(sorted_list)   (high(sorted_list) - low(sorted_list)) ) // 2
    return mid_index


for x in range(4):
    if list[mid(list)] < key:
        list = list[mid(list) 1:]
    elif list[mid(list)] < key:
        list = list[mid(list)-1:]
    print(list)

I know I should not keep a range number in for loop but I know it will only make 4 comparisons in this example so I hardcoded it. But when I run it, it splits the list only once and keep on printing the second half of the list. Output image:

CodePudding user response：

Ok, I tried your code and had to do a few corrections:

• The while loop had to be modified (you knew that)
• There wasn't a check for the case where the key is found (see comments)
• There was a typo, < instead of > (see comments)
• In the same line, the list partition was wrong
• The low function was useless (returning a constant value) (see comments)
• The high function was useless too (simply returning the value from another function)
• The mid function was more complicated than needed (it boiled down to taking a value, then adding and subtracting zero), so it can simply take the value

Ah, btw the input list is not sorted in your example.

This is my proposal:

def mid(lst):
    return len(lst) // 2

def bin_search(lst, k):
    while lst:
        i = mid(lst)
        if lst[i] == k:
            return True
        if lst[i] < k:
            lst = lst[i 1:]
        elif lst[i] > k:
            lst = lst[:i]
    else:
        return False

bin_search([3,6,8,12,14,17,25,29,31,36,42,47,55,62,63], 42)
True

bin_search([3,6,8,12,14,17,25,29,31,36,42,47,55,62,63], 58)
False