Binary Search in python

Question

I tried writing a python code that does binary search. After I got errors, I looked up other people's implementations on binary search, but I don't understand why mine causes errors.

my_list = list(range(30));

def search(numbers, target):
    minimum = 0
    maximum = len(numbers) - 1
    average = (maximum + minimum) // 2

    try:

        index = 0
        for num in numbers:
            if numbers[index] <= numbers[index+1]:
                continue
            else:
                break
            index += 1

    except UnicodeError:
        print("The list is not sorted")

    else:
        if target == average:
            print numbers.index(average)
        if target < average:
            search(numbers[0:numbers.index(average)-1], target)
        else:
            search(numbers[numbers.index(average):maximum], target)

search(my_list, 10)

Could you please tell me what I did wrong and also how to fix it? Thank you so much!!

Answer 1 · 2016-05-11T12:02:08Z

May 11, 2016 12:02pm

Since you are slicing the list you won't be able to find the correct index of the found item in the list. Also, the current code fails when the item is not in the list. I think a better approach is to add two more parameters to the function, one that is the index of the first item in the list and one that is the index of the last item in the list. Then instead of slicing the list we can just manipulate these two values. Also, it is better to have the list just return the index without any printing and return -1 if the item is not found. Then you can pass the return value to print(). Here's my new code:

my_list = [1, 3, 5, 7, 9, 11, 13, 15]

def search(numbers, target, first, last):
    mid = (first + last) // 2
    if first > last:
        index = -1
    elif target == numbers[mid]:
        index =  mid
    elif target < numbers[mid]:
        index = search(numbers, target, first, mid-1)
    else:
        index = search(numbers, target, mid+1, last)
    return index

print(search(my_list, 7, 0, len(my_list)-1))
print(search(my_list, 10, 0, len(my_list)-1))

Answer 2 · 2016-05-10T17:23:26Z

May 10, 2016 5:23pm

A few things I noticed:

In the for loop the line index += 1 is never reached. You need to move it to the if block before continue.
After you've fixed the problem above you will get a "list index out of range error" because in the last iteration of the loop index is 29 which means index+1 would be 30, which causes the error.
It looks like that in the for loop you're making sure the list is sorted but this is done each time that search is called, which is unnecessary in the subsequent recursive calls to search. You may want to do that check before calling search, or sort the list before calling search(my_list, 10).
Instead of comparing target to average you need to compare it to numbers[average] since average is the index of the middle of the list.
To slice the list when target is less than the number in the middle of the list use: numbers[0: average]
To slice the list when target is greater than the number in the middle of the list use: numbers[average+1:]

Here's my code without the part that makes sure the list is sorted:

my_list = list(range(30))

def search(numbers, target):
    minimum = 0
    maximum = len(numbers) - 1
    average = (maximum + minimum) // 2

    if target == numbers[average]:
        print(numbers[average])
    elif target < numbers[average]:
        search(numbers[0:average], target)
    else:
        search(numbers[average + 1:], target)


search(my_list, 10)

One last point, as it is the code does not take care of the case where target is less than 0 or greater that 29.

Welcome to the Treehouse Community

Looking to learn something new?

Derek Derek

Derek Derek

Binary Search in python

2 Answers

Kourosh Raeen

Kourosh Raeen

Derek Derek

Derek Derek

Kourosh Raeen

Kourosh Raeen

Derek Derek

Derek Derek