MITx: 6.00.1x Introduction to Computer Science and Programming Using Python Week 2: Simple Programs 4. Functions

ESTIMATED TIME TO COMPLETE: 18 minutes

We can use the idea of bisection search to determine if a character is in a string, so long as the string is sorted in alphabetical order.

First, test the middle character of a string against the character you're looking for (the "test character"). If they are the same, we are done - we've found the character we're looking for!

If they're not the same, check if the test character is "smaller" than the middle character. If so, we need only consider the lower half of the string; otherwise, we only consider the upper half of the string. (Note that you can compare characters using Python's < function.)

Implement the function isIn(char, aStr) which implements the above idea recursively to test if char is in aStr. char will be a single character and aStr will be a string that is in alphabetical order. The function should return a boolean value.

As you design the function, think very carefully about what the base cases should be.

def isIn(char, aStr):

'''

char: a single character

aStr: an alphabetized string

returns: True if char is in aStr; False otherwise

''' 这是我写的答案：

# Your code here

if len(aStr) == 0:

　　return False

elif len(aStr) == 1:

　　if aStr == char:

　　　　return True

　　else:

　　　　return False

else:

　　if char == aStr[len(aStr)//2]:

　　　　return True

　　elif char < aStr[len(aStr)//2]:

　　　　return isIn(char, aStr[:len(aStr)//2])

　　else :

　　　　return isIn(char, aStr[len(aStr)//2+1:])

def isIn(char, aStr):
   ''' 这是标准答案：
   char: a single character
   aStr: an alphabetized string
   
   returns: True if char is in aStr; False otherwise
   '''
   # Base case: If aStr is empty, we did not find the char.
   if aStr == '':
      return False

   # Base case: if aStr is of length 1, just see if the chars are equal
   if len(aStr) == 1:
      return aStr == char

   # Base case: See if the character in the middle of aStr equals the 
   #   test character 
   midIndex = len(aStr)//2
   midChar = aStr[midIndex]
   if char == midChar:
      # We found the character!
      return True
   
   # Recursive case: If the test character is smaller than the middle 
   #  character, recursively search on the first half of aStr
   elif char < midChar:
      return isIn(char, aStr[:midIndex])

   # Otherwise the test character is larger than the middle character,
   #  so recursively search on the last half of aStr
   else:
      return isIn(char, aStr[midIndex+1:])

虽然第一次看这道题时，我是懵逼的，不太懂题目的意思。但是我再看第二遍的时候，我突然理解了题意：用二分法和递归在从小到大排列的字符串中找出要求的字符。最后我的答案是正确的，可以看出：我和答案的思想是一样的，但是它写的比我简练，这点需要学习。