how to search a number using binary search algorithm (without implementing any function) in python

Question

Below is my complete code for binary search written in python3 version. I was able to:-i) create a list, ii) sorted the list using bubble sort algorithm, iii)wrote code snippet for searching a number using binary search, But while searching for any number (which is present/not present in the list), my code goes into an infinite loop and does not gives any result. I tried looking for the error,But was unable to debug the code.

Also, how to get the index of the number in list? I thought of using list.index() method. Can it work in case of sorted list or my index number output will be wrongly displayed?

list=[]
item=0
while item!="99":
    item=input("Enter the number, To discontinue enter 99:")

    if item.isdigit(): #isdigit() checks whether input string consists of digits only
        list.append(int(item)) #convert the input string into number
    else:
        list.append(item)

del list[-1] #Delete the number at last index of the list. It will delete "99",
             #which we have used to discontinue the loop

print("The unsorted list is: ",list)

#Using bubble sort algorithm to sort the list
length=len(list)

for i in range(length):
    for j in range(length-1):
        if list[j]>list[j+1]:
            list[j],list[j+1]=list[j+1],list[j]

print("Our sorted list is: ",list)

#Implementing binary serach algorithm

target=int(input("Enter the number you are looking for: "))
first=0              #First index of list is 0
last=len(list)-1     #Last index of list is "length of list minus 1"
mid=(first+last)//2

while first<=last:
    if list[mid]<target:        #If element at middle index is less than the target element,shift new lower index to one more than middle index
        low=mid+1                     
    elif list[mid]==target:     #else, if element at middle index is same as target element
        print("Number is found at index")
        break
    else:
        last=mid-1
    mid=(first+last)//2
    if (first>last):
        print("Number not found in list")

What is the motivation for not implementing any function? That seems like an arbitrary restriction which is almost guaranteed to lead to bad code. — John Coleman
– John Coleman, Commented Jun 16, 2016 at 19:16
From the context, I bet this is homework, and what actually was in the question is he should not use a standard python function, but that bit got misinterpreted. — spectras
– spectras, Commented Jun 16, 2016 at 19:31
You sometimes use first and sometimes low in your code. Probably the origin of the bug. Choose which it is and rename the other. — spectras
– spectras, Commented Jun 16, 2016 at 19:35
It is a part of assignment only and focused on to get it done without implementing function including standard python built ins. — Amritanshu Verma
– Amritanshu Verma, Commented Jun 17, 2016 at 8:10

Garrigan Stafford · Accepted Answer · 2016-06-16 19:19:36Z

1

The infinite loop is from the line

low=mid+1

I think what you meant was

last=mid+1

The error was that the case list[mid]<target would happen, but since low is being changed not last, mid never changes the case will be triggered again on the next iteration.

EDIT: Also note that mid is the index of the number in the list

answered Jun 16, 2016 at 19:19

Garrigan Stafford

1,4031 gold badge11 silver badges20 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Amritanshu Verma Over a year ago

You were absolutely right. Thanks for that catch. Perhaps I got messed up with so many terms(first, last, mid) and complex algorithm and made that mistake...

Collectives™ on Stack Overflow

how to search a number using binary search algorithm (without implementing any function) in python

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related