Skip to main content
Engineering LibreTexts

22.3: Search

  • Page ID
    15406
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    All of the exercises in the previous section have something in common; they can be solved with the search pattern we saw in Section 8.6. The simplest example is:

    def has_no_e(word):
        for letter in word:
            if letter == 'e':
                return False
        return True
    

    The for loop traverses the characters in word. If we find the letter “e”, we can immediately return False; otherwise we have to go to the next letter. If we exit the loop normally, that means we didn’t find an “e”, so we return True.

    avoids is a more general version of has_no_e but it has the same structure:

    def avoids(word, forbidden):
        for letter in word:
            if letter in forbidden:
                return False
        return True
    

    We can return False as soon as we find a forbidden letter; if we get to the end of the loop, we return True.

    uses_only is similar except that the sense of the condition is reversed:

    def uses_only(word, available):
        for letter in word: 
            if letter not in available:
                return False
        return True
    

    Instead of a list of forbidden letters, we have a list of available letters. If we find a letter in word that is not in available, we can return False.

    uses_all is similar except that we reverse the role of the word and the string of letters:

    def uses_all(word, required):
        for letter in required: 
            if letter not in word:
                return False
        return True
    

    Instead of traversing the letters in word, the loop traverses the required letters. If any of the required letters do not appear in the word, we can return False.

    If you were really thinking like a computer scientist, you would have recognized that uses_all was an instance of a previously-solved problem, and you would have written:

    def uses_all(word, required):
        return uses_only(required, word)
    

    This is an example of a program development method called problem recognition, which means that you recognize the problem you are working on as an instance of a previously-solved problem, and apply a previously-developed solution.


    This page titled 22.3: Search is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by Allen B. Downey (Green Tea Press) .

    • Was this article helpful?