递归方法

    1. # coding:utf-8
    4. def binary_search(a_list, key):
    5.     n = len(a_list)
    6.     if n == 0:
    7.         return False
    8.     mid = n//2
    9.     if a_list[mid] == key:
    10.         return True
    11.     elif a_list[mid] < key:
    12.         return binary_search(a_list[mid+1:], key)
    13.     else:
    14.         return binary_search(a_list[:mid], key)
    17. if __name__ == "__main__":
    18.     test_list = [1,1,2,3,5,8,13,21,34,55,89,144]
    19.     print(binary_search(test_list, 3))

    非递归方法

    1. # coding:utf-8
    4. def binary_search(a_list, key):
    5.     n = len(a_list)
    6.     if n == 0:
    7.         return False
    8.     start = 0
    9.     end = n-1
    10.     while end >= start:
    11.         mid = (end+start)//2
    12.         if a_list[mid] == key:
    13.             return True
    14.         elif a_list[mid] < key:
    15.             start = mid + 1
    16.         else:
    17.             end = mid - 1
    18.     return False
    21. if __name__ == "__main__":
    22.     test_list = [1,1,2,3,5,8,13,21,34,55,89,144]
    23.     print(binary_search(test_list, 24))