数据结构与算法全套精讲(python版) (六)二分查找

以你之姓@ 2021-12-17 01:04 212阅读 0赞

使用前提：有序、顺序表

最坏的情况就是一直在对半找下去，2的m次幂(m即查找次数)为n(总长)，即时间复杂度m为O(logn)；最好的情况就是首次就找到，即O(1)

![20190706232023482.png][]

1.  递归法( 类似于f(n)与f(n-1)、f(n-2) )

def BinarySearch(arr, item):
        n = len(arr)
        mid = n // 2
        if n > 0:
            if arr[mid] == item:
                return True
            elif item < arr[mid]:
                '做递归调用时一定要不要忘return！'
                return BinarySearch(arr[:mid], item)
            else:
                return BinarySearch(arr[mid+1:], item)
        return False
    
    arr0 = input('请输入有序数列，用空格隔开：\n')
    item1 = input('请输入待搜索数字：\n')
    arr0 = arr0.split()
    arr1 = []
    for k in arr0:
        # print(type(k))
        arr1.append(int(k))#输入的i如果不加int会认为是字符!
    print(BinarySearch(arr1,int(item1)))

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70][]

2. 非递归：

def BinarySearch(arr, item):
        n = len(arr)
        head = 0#初始头尾的位置索引
        rear = n-1
        while head <= rear:
            mid = (head + rear) // 2
            if arr[mid] == item:
                return True
            elif item < arr[mid]:
                rear = mid - 1
            else:
                head = mid + 1
        return False
    
    arr0 = input('请输入有序数列，用空格隔开：\n')
    item1 = input('请输入待搜索数字：\n')
    arr0 = arr0.split()
    arr1 = []
    for k in arr0:
        # print(type(k))
        arr1.append(int(k))#输入的i如果不加int会认为是字符!
    print(BinarySearch(arr1,int(item1)))

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 1][]

[20190706232023482.png]: /images/20211214/387a2246b5fa44d6a4f4ceaa5aa79492.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70]: /images/20211214/dbb62ffe8efe4dcc9f0dbab1795de2e8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5OTM4NjY2_size_16_color_FFFFFF_t_70 1]: /images/20211214/5299fa5f9eaf4a9692e4e3ed231e1f4b.png