I'm building a Python spell checker that reads words from a text file and compares them with an alphabetically sorted dictionary file. Any words not found should be added to an absent list and printed at the end. I'm using binary search, but the program seems to compare only the last word from the input file. I'm also unsure where the present and absent lists should be updated. What is wrong with my loop structure and binary-search logic?
3 Answers
Your result lists should be updated only after the binary search finishes. At the moment, the append statements appear to run during each iteration of the search, and absent is being updated regardless of whether the word was found. Use the found flag after the search: if found, append the word to present; otherwise append it to absent. Also use `while lo <= hi`, since the final remaining index still needs to be checked.
The indentation is important here because it determines which statements run inside the loops. Make sure the code is posted with its original indentation, then add a few temporary print statements for firstLst, each input word, lo, hi, and mid. That will show whether every word is being read and whether the search is progressing as expected.
A basic structure would look like this: `for word in firstLst: lo, hi = 0, len(secondLst) - 1; found = False; while lo <= hi: mid = (lo + hi) // 2; if secondLst[mid] == word: found = True; break; elif secondLst[mid] < word: lo = mid + 1; else: hi = mid - 1; if found: present.append(word); else: absent.append(word)`. Keep the loops that read both files separate from this search loop. Also confirm that both lists use matching capitalization and that dictionary entries do not contain trailing newline characters.
So the file-reading loops should stay before the binary search, and only the list updates should move below the search loop?