How To Implement A Binary Search?

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

Solution 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 listif 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 sortingexit()     #to stop through infinite loopingelif 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)

Solution 2:

So from the sound of your question you are attempting to get a binary search working for your example. First, it is useful to know that a binary search only works reliably on sorted data. This is quite different than a standard linear search that will always find the value, regardless of order. As you likely already know binary search is preferred because it eliminates half of the potential candidates per iteration, whereas linear search only eliminates one element. With that said, let's discuss the modifications I have made to your program. First, some cosmetic changes can greatly increase the clarity of your program.

1.) Using descriptive variable names is very important and serves as a note to others reading your code, on what the contents and function of a variable might be. This is especially important in a language like python where variable types are not easily inferred just by reading the code. So instead of reusing the variable i multiple times, I have renamed your function parameter target as that is the search term we are attempting to locate, i.e. our 'target'. I also renamed your function from 'bsort' which implies that the function sorts something, to 'bsearch' which is a more appropriate name because it more accurately describes what the function does.

2.) Binary search can be implemented using a loop or recursion. For simplicity, I have selected the iterative route using a loop. As I mentioned before, binary search works by eliminating half of the potential search candidates each iteration. Without the loop, you do eliminate half of the candidates (only one time), but unless you are extremely lucky you will likely not find the term you are searching for! Instead you need to continue this process until you have located the term you are searching for. This is the function of the while True: loop.

3.) Finally, we have made sure that we are using integers to access the indices of our list. All lists in python are indexed from 0 to n-1 where n is the number of elements in a list. We cannot access a list using a floating point value such as 2.5 because this does not correspond to any specific 'slot' in the list. Similarly, we cannot use a string to access our elements because a list again requires a integer to perform a lookup. This is the purpose of mid = int((left + right)/2).

With all that said, this should work for your intended purpose. I hope this helps you! I also encourage you to take a look at some examples of how to implement a binary search such as this one.

defbsearch(alist, target):
    left = 0
    right = len(alist)-1whileTrue:
        mid = int((left + right)/2)
        if alist[mid] < target :
            left = mid + 1elif alist[mid] > target :
            right = mid + 1elif alist[mid] == target :
            print ("word '" + target + "' found at " + str(mid))
            breakelif left > right:
            print ("Not Found!")
            break       


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

Solution 3:

First it is == which checks for equality and does not assign a value. Use single = instead of == for assignment.

Also, your method takes i as a string and then uses a string to refer to an index of list. That generates the error.

You are using binary search's integer approach to find strings which is not correct. Specially because your strings are neither sorted by length, nor by alphabetical order. Refer to some other methods to do this.

See Binary string search in Python 3.x