Python Forum

Full Version: binary search string help
You're currently viewing a stripped down version of our content. View the full version with proper formatting.
Hi! I'm trying to look for a word in my list by way of binary search. But sth doesn;t work. Can sb have a look at it? ;) Thanks!

infile = open("clean.acc", "r")

firstlist = []
for line in infile:
    firstlist.append(line)

first = 0
last = len(firstlist)-1
done = False 

acc = input("Enter your acc nr")

while first<=last and not done:
    mid = (first+last)//2
    if firstlist[mid] == acc:
        done = True
        print(done)
    else:
        if firstlist[mid] > acc:
            last = mid-1
        else: 
            first = mid+1


infile.close()
Just a little refactoring and it works. I restructured the if statements into a single if...elif...else. The main problem was the mid assignment. Dividing by 2 generates a float and floats cannot be used in indexing; the interpreter would raise an error when trying firstlist[mid] because it's firstlist[4.5] (supposing a nine item list).

infile = open("clean.acc", "r")

firstlist = []
for line in infile:
    firstlist.append(line)

first = 0
last = len(firstlist)-1
done = False 

acc = input("Enter your acc nr")

while first<=last and not done:
    mid = int((first+last)//2)

    if acc < firstlist[mid]:
        first = mid
    elif acc == firstlist[mid]:
        done = True
        print(done)
    else:
        last = mid

infile.close()