python, string comparison not working?

Question

I have been tasked with creating a binary search over a list of words, I have come up with 2 implementations (and clearly haven't put in a case where the word isn't found yet but that's not an issue yet), however when the list is narrowed down to the word I am looking for, my function does not finish, instead it keeps running until maximum recursive depth is exceeded.

I put in print and it clearly shows the word at dasList[mid], and shows this over and over again until it finally gives up.

def _bisect2(dasList, word):
    mid = int(len(dasList)/2)
    if word.lower() > dasList[mid].lower():
        return _bisect2(dasList[mid: len(dasList)], word)            
    if word.lower() < dasList[mid].lower():
        return _bisect2(dasList[0: mid], word)
    else:
        return mid

this is being called by

print(_bisect2(fileList, input('Please type a word')))

I am using the Python 3.0 interpretor. Any suggestions?

The standard library already includes a bisect module. Is this homework? — Karl Knechtel
– Karl Knechtel, Commented May 31, 2012 at 3:50

mgilson · Accepted Answer · 2012-05-31 02:00:39Z

1

Your implementation (almost) works for me (and doesn't show the behavior you described with my pre-sorted input). I assume you've sorted your input files? A slightly modified (working) example is posted below.

def _bisect2(dasList, word,lidx=0):
    mid = int(len(dasList)/2)
    if word.lower() > dasList[mid].lower():
        return _bisect2(dasList[mid:], word,lidx=lidx+mid)            
    elif word.lower() < dasList[mid].lower():
        return _bisect2(dasList[:mid], word,lidx=lidx)
    return lidx+mid

words=sorted(["one","two","three","four","five","twenty","foo"])
print (words)
print (_bisect2(words,'three'))

Note that you were returning the index in the last partial list (which will always be 0)...

edited May 31, 2012 at 2:00

answered May 31, 2012 at 1:37

mgilson

312k70 gold badges656 silver badges722 bronze badges

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

9 Comments

Tony Over a year ago

yes the list of words is already sorted, and yes you're right it would return a 0. What i did notice however is the word i input seems to append a space onto the end. why would that be?

mgilson Over a year ago

Well, that'll do it ;) Then your word isn't in the list. Just strip your input and you should be OK.

Tony Over a year ago

cool thanks. ^^ why would it append it? is it just the newline character being added after enter is pressed?

mgilson Over a year ago

@Tony -- I'm not sure. try using raw_input instead of input -- since you want strings, that's probably safer anyway.

Tony Over a year ago

by all accounts 'raw_input()' has been changed to input stackoverflow.com/questions/954834/… and after investigating '.strip()' I ran into '.rstrip()' which did the job as well. Thanks for your help!

|

Josh Smeaton · Accepted Answer · 2012-05-31 01:49:03Z

1

This works fine for me. Note that the index returned at the end will always be the index of the word in the minimal list, not the index of the original list.

See also that the > compare doesn't do a len over the list again, it just iterates to the end. Slice syntax allows you to leave off the last number if you're iterating to the end.

words = "The quick brown fox jumped over the lazy dog".split()

def bisect(words, word):
    mid = int(len(words)/2)
    if word.lower() > words[mid].lower():
        return bisect(words[mid:], word)
    elif word.lower() < words[mid].lower():
        return bisect(words[0:mid], word)
    return mid

words = sorted(words)
print bisect(words, 'dog')

answered May 31, 2012 at 1:49

Josh Smeaton

48.8k24 gold badges137 silver badges165 bronze badges

Comments

Steven Rumbalski · Accepted Answer · 2012-05-31 02:18:31Z

1

Why not use Python's bisect module?

Recipe from the docs:

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

Example:

>>> a = ['alfred','edward','mary','susan','thomas','wilma']
>>> index(a, 'mary')
2
>>> index(a, 'martha')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 6, in index
ValueError

answered May 31, 2012 at 2:18

Steven Rumbalski

45.7k10 gold badges96 silver badges125 bronze badges

2 Comments

Tony Over a year ago

because it's more fun to figure out implementations ^^

Steven Rumbalski Over a year ago

@Tony: Fair enough. If speed is critical, use the bisect module.

Collectives™ on Stack Overflow

python, string comparison not working?

3 Answers 3

9 Comments

Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

9 Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related