CODEWITHSUNDEEP
pythonlistsearchcounter
Altaic
Altaic

Reputation: 55

Binary search in Python not working properly, only displaying some items in list

My code isn't working properly and is only displaying the correct results of 3 items and not the one in the 2nd index. I wouldn't have posted but I went from the pseudocode given on the GCSE bitesize page for CS which isn't working when I convert in Python. https://www.bbc.co.uk/bitesize/guides/zm77xfr/revision/3

my_list=['arnold', 'matt', 'david', 'james']

found = False
search_item = input("type a name to find")
start_range = 0
end_range = len(my_list)



while found == False and start_range <= end_range:
    mid = (start_range + end_range) //2

    if search_item == my_list[mid]:
        found == True
        print("item found")
    else:

        if my_list[mid] >= search_item:
            end_range = mid -1
        else:
            start_range = mid +1


if found == False:
    print("item not found")

When I run the code above and type in 'arnold', I get an 'item found' message printed infinitely which is fine for now. However, if I type in the second item from the list, in this case 'matt', I get an 'item not found' message display

If I type in 'david' or 'james' it works as well, so it's only the item in the 2nd index.

I initially converted the GCSE bitesize pseudocode in python but it didn't even work. I'm really confused, I have no clear idea to why it's not working but have a feeling it has something to do with the index or even the mid variable.

Could someone direct me on which part to check?

Upvotes: 0

Views: 53

Answers (1)

ATK7474
ATK7474

Reputation: 349

You've got a few issues here that needed to be addressed. First of all, binary search requires the list to be sorted, so that the comparisons (ie my_list[mid] >= search_item) make sense. Next, you need to change found == True to found = True. The way you have it is just a comparison, not setting the value to True.

It should look like this:

my_list=['arnold', 'matt', 'david', 'james']

found = False
search_item = input("type a name to find")
start_range = 0
end_range = len(my_list) - 1

# ADD THIS
my_list.sort()

while found == False and start_range <= end_range:
    mid = (start_range + end_range) //2

    if search_item == my_list[mid]:
        # CHANGE THIS
        found = True
        print("item found")
    else:

        if my_list[mid] >= search_item:
            end_range = mid -1
        else:
            start_range = mid +1

if found == False:
    print("item not found")

Upvotes: 1

Related Questions