-4

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)
Improve this question
6
  • 3
    What do you mean an address? Commented Jan 26, 2017 at 21:27
  • 3
    What would the input be? i is an index, which must be an integer. Also note that bisection search isn't much help on an unordered sequence. Commented Jan 26, 2017 at 21:27
  • How can I make it work please? Commented Jan 26, 2017 at 21:31
  • Well it depends...what is your use case? Are you trying to get fast lookup in a list or are you just trying to sort your list? If your goal is the former, then you should sort your list using list.sort() and then perform a binary search over it. If it is the latter, then you need to spend some time working on your code. Commented Jan 26, 2017 at 21:35
  • mid, not [mid]. Commented Jan 26, 2017 at 22:52

3 Answers 3

Reset to default
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)

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

3 Comments

using blist.index() causes python to search through the array again using a linear search...effectively eliminating the entire purpose of the bsearch. Why not just print out the value of mid?
but simply printing out m gives new location of element i... thus it depends whether the problem is to just find out whether or not the element is in the list or is to print the location of the element in the original list. If the problem falls under category 1, then it is not even necessary to print m, 'yes' or 'no' would do the work.
Thank you for your help my problem is 'catagory 1' to find whether an item is in the list .
0

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.

def bsearch(alist, target):
    left = 0
    right = len(alist)-1

    while True:
        mid = int((left + right)/2)
        if alist[mid] < target :
            left = mid + 1
        elif alist[mid] > target :
            right = mid + 1
        elif alist[mid] == target :
            print ("word '" + target + "' found at " + str(mid))
            break
        elif left > right:
            print ("Not Found!")
            break       


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

2 Comments

I know it needs to be a sorted list, I was trying to assine a number to each of the variables in the list. So if the list is 0,1,2,3,4 it would split at 2 if 'target' is less than 2 then it would half it again. Say 0 was the target it would divide until it gets 0 which would correspond to the word. But .sort also works too. Thank you for your help
So that is actually exactly what is going on here! Your solution was close from an algorithmic perspective, you really just needed to add the loop. If the list was [0,1,2,3,4] and our target is 0 then the items 'checked' will be 2, 1, 0 at which point our target has been found.
0

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

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.