题目标题

二分查找

参考解析
  1. def binary_search(alist, item):
  2. """二分查找 非递归方式"""
  3. n = len(alist)
  4. start = 0
  5. end = n - 1
  6. while start <= end:
  7. mid = (start + end) // 2
  8. if alist[mid] == item:
  9. return True
  10. elif item < alist[mid]:
  11. end = mid - 1
  12. else:
  13. start = mid + 1
  14. return False
  15. def binary_search_2(alist, item):
  16. """二分查找 递归方式"""
  17. n = len(alist)
  18. if 0 == n:
  19. return False
  20. mid = n // 2
  21. if alist[mid] == item:
  22. return True
  23. elif item < alist[mid]:
  24. return binary_search_2(alist[:mid], item)
  25. else:
  26. return binary_search_2(alist[mid + 1:], item)
  27. if __name__ == '__main__':
  28. li = [17, 20, 26, 31, 44, 54, 55, 77, 93]
  29. # print(binary_search(li, 55))
  30. # print(binary_search(li, 100))
  31. print(binary_search_2(li, 55))
  32. print(binary_search_2(li, 100))