python - How to implement a binary search?

Question

I'm trying to create a binary search function, I've attempted it with the code below but am a beginner at python ; I'm getting the error "list indices must be integers, not str" on the line i == alist[i]. Could you please help me fix the problem? Here's the whole code:

def bsort(alist, i):
    left = 0
    right = len(alist)-1
    i == alist[i]

    [mid] = (left + right)//2

    if alist[mid] < i :
        left = [mid] + 1

    elif alis[mid] > i :
        right = [mid] + 1

    elif alist[mid] == i :
        print ("word found at", i )

    elif left > right:
        print ("Not Found!")       


i = input("Enter a search >")
alist = ["rat","cat","bat","sat","spat"]
bsort(alist, i)

Answer 1

you are getting 'list indices must be integers, not str' because you are taking a string as input for binary search in the list and in 4th line using it as an index to the list which is causing the error since the list is indexed through integer.

Another issue(s): 1. your list must be sorted before applying binary search, 2.line 6 cause another error because int object is not iterable. 3.and in order to make a complete search through the list, u must include a while loop, which will sense for your first two if condition and help in looping through the list.

Might this code will help you:

def bsort(alist,blist,i):

left = 0
right = len(alist)-1

mid = (left + right)//2

while left <= right:    #  loop through the list
    if alist[mid] < i :
        left = mid + 1
    elif alist[mid] > i :
        right = mid + 1
    elif alist[mid] == i :
        print ("word found at", blist.index(i) )    # will print the original index of element i.e. before sorting
        exit()     #to stop through infinite looping
    elif left > right:
        print ("Not Found!")       

i = input("Enter a search >") #string u want to search alist = ["rat","cat","bat","sat","spat"] blist = alist[:] # creating another list to have knowledge of element index in original list alist.sort() # sorting list to perform binary search bsort(alist,blist,i)