Python Binary Search

Question

I'm a beginner programmer and I wanted to make my own binary search algorithm from scratch without any help. It's safe to say it's not going well. I was hoping someone could find the error in my code. I fixed a few issues, but now I've ran into the issue where if can't find values greater than the middle index, and it is not ending once it reaches a single value not equal to the target.

    import random

userInput = 100
numbers = []

for i in range(100):
    numbers.append(random.randint(0, 100))

#Adding 100 to use as a test
numbers.append(100)
numbers.sort()
print(numbers)

def binarySearch(list, target):
    midIndex = int(len(list)/2)
    midValue = list[midIndex]

    if midValue == target:
        print("We found " + str(target))

    elif target > midValue:
        newList = numbers[midIndex:]
        binarySearch(newList, target)

    elif target < midValue:
        newList = numbers[:midIndex]
        binarySearch(newList, target)

    elif len(list) == 1 and list[0] != target:
        print(target + " is not in the list")

    else:
        print("It's not in the list")

binarySearch(numbers, userInput)

Answer 1

There are two main issues with your code:

1. mid is being used to represent both an index and a value.
2. The end of binarySearch() is never reached.

Issue #1: mid

When creating newList using a slice of list, you are using mid as an index:

elif target > mid:
    newList = numbers[mid:]

However, mid is not an index. It is the value in the middle of list:

mid = list[int(len(list)/2)]

Try using two variables:

midIndex = int(len(list)/2)
midValue = list[midIndex]

Issue #2: binarySearch()

binarySearch() never reaches the final elif to see if target is not in the list.

The final elif is only reached after checking the following conditions:

if midValue == target:
    ...
elif target > midValue:
    ...
elif target < midValue:
    ...

Clearly, if midValue and target are two numbers, one of these comparisons must return True.

Because of the order of the checks performed, binarySearch() never ends up getting to this section:

elif len(list) == 1 and list[0] != target:
    ...

To fix this issue, try rearranging your if statements so that binarySearch() reaches this part of the code.