在Python 3

Question

以下搜索字符的字符串，是一個程序，我必須爲學校工作的，在此我們必須用我所概述的風格，但想不通爲什麼程序總是返回string not found。任何想法，爲什麼這是這樣做？我應該使用測試功能和一個調試器，但是這是超越我。我修正了崩潰的程序的遞歸問題。

def str_search(data, target, start, end): 
    """ 
    str_search : String String NatNum NatNum -> NatNum or NoneType 
    Description: 
    Search for a target value in a sorted data string. 
    The search happens between the start and end indices inclusively. 
    This starts searching in the middle. If it finds the target, it is done. 
    Otherwise it decides whether to search the first half or the second half. 
    preconditions: the data string is in ascending alphanumeric order. 
    Parameters: 
     data - a string 
     target - the target value to find is a single character string e.g. 'Q' 
     start - the starting index into the data 
     end - the ending index into the data 
    Returns: 
     index of target in data, if present; otherwise None. 
    """ 

    if start <= end: 
     return None 

    mid_index = (start + end) // 2 
    mid_value = data[mid_index] 

    # debug statement prints the data. 
    #print("Searching for", target, ":", data[start:mid_index], 
    # "*" + str(mid_value) + "*", data[mid_index+1:end+1]) 

    if target == mid_value: 
     return mid_index 
    elif target <= mid_value: 
     return str_search(data, target, start, mid_index - 1) 
    else: 
     return str_search(data, target, mid_index, end) 


def find_target(data, target): 
    """ 
    find_target : String String -> NatNum or NoneType 
    find_target returns the index of target in data or None if not found. 
    Parameters: 
     data - a string 
     target - the target value to find 
    Returns: 
     The index of the target element in data, if present, or None. 
    """ 

    return str_search(data, target, 0, len(data) - 1) 


def makeString(): 
    """ 
    makeString :() -> String 
    makeString returns a String 
    """ 
    data = "" 
    # append characters to make the string 
    for num in range(36, 108, 2): 
     data += chr(num) 
    return data 


def main_search(): 
    """ 
    main_search : Void -> NoneType 
    """ 

    data = makeString() 
    print("Number of elements: ", len(data)) 

    while True: 
     print("\nData: ", data) 
     target = input("Enter a character to find: ") 

     if target == "": 
      break 
     else: 
      index = find_target(data, target) 
      print() 
      if index != None: 
       print(target, "found at index", index) 
      else: 
       print(target, "not found") 
       # end while 


def test_str_search(): 
    """ 
    a suite of pass/fail test cases to validate that str_search works. 
    """ 
    # Complete this test function. 
    pass 

####################################################################### 
# 3.3. Document your debugging results trying to fix the str_search code. 
# Enter answers to the questions below inside the triple-quoted string. 
""" 
    Were you able to completely fix str_search? 
    If not, explain in detail the cases that still fail. 
    What tool(s) did you use? 
    What went well? 
    What problems did you have? 
""" 
####################################################################### 

if __name__ == "__main__": 
    # 
    # Run the test functions for problem 1, problem 2, and problem 3. 
    # 
    #test_create_multiplication_table() 
    #test_is_palindrome() 
    #test_is_reverse_of() 
    test_str_search() 
    # 
    main_search() 

Answer 1

在你的搜索功能，你有這樣的

if start <= end: 
     return None 

但你開始爲0，並最終被LEN（數據） - 1，這就是爲什麼你搜索函數返回什麼所有的時間。

Answer 2

這是有趣的，你需要測試，如果你已經達到了目的，向前或向後的二進制搜索您聲明沒有被發現之前，你必須確保一旦你已經達到了搜索結束了答案並不是隱藏在任何一端。你應該得到你想要的以下內容：

if end - start <= 1: 
    if target == data[end]: 
     return end 
    elif target == data[start]: 
     return start 
    else: 
     return None