BinarySearch.py

"""
1. 二分查找是有条件的，首先是有序，其次因为二分查找操作的是下标，所以要求是顺序表
2. 最优时间复杂度：O(1)
3. 最坏时间复杂度：O(logn)
"""
# def binary_search(nums, data):
#     """
#     非递归解决二分查找
#     :param nums:
#     :return:
#     """
#     n = len(nums)
#     first = 0
#     last = n - 1
#     while first <= last:
#         mid = (last + first) // 2
#         if nums[mid] > data:
#             last = mid - 1
#         elif nums[mid] < data:
#             first = mid + 1
#         else:
#             return True
#     return False


def binary_search(nums, data):
    """
    递归解决二分查找: nums 是一个有序数组
    :param nums:
    :return:
    """
    n = len(nums)
    if n < 1:
        return False
    mid = n // 2
    if nums[mid] > data:
        return binary_search(nums[:mid], data)
    elif nums[mid] < data:
        return binary_search(nums[mid+1:], data)
    else:
        return True

if __name__ == '__main__':
    nums = [1, 4, 6, 8, 10, 20, 25, 30]
    if binary_search(nums, 8):
        print('ok')