数据结构之二分查找（折半查找）

二分查找又称折半查找，优点是次数比较少，查找速度快，平均性能好，其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等即查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则查找后一子表。重复以上过程，直到找到满足条件的记录，便查找成功，或直到子表不存在未知，此时查找不成功。

二分查找算法分析

使用前提：有序、顺序表

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

二分查找算法实现

示例代码1：

def binary_search(li, item):
    """二分查找"""
    n = len(li)
    mid = n // 2
    if n > 0:
        if li[mid] == item:
            return True
        elif li[mid] > item:
            return binary_search(li[:mid], item)
        else:
            return binary_search(li[mid + 1:], item)
    return False


if __name__ == '__main__':
    li = [17, 20, 26, 31, 44, 50, 54, 77, 93]
    result1 = binary_search(li, 20)
    print(result1)
    result2 = binary_search(li, 78)
    print(result2)

运行结果：

示例代码2：

#  非递归
def binary_search(li, item):
    """二分查找"""
    n = len(li)
    first = 0
    end = n - 1
    while first <= end:
        mid = (first + end) // 2
        if li[mid] == item:
            return True
        elif li[mid] > item:
            end = mid - 1
        else:
            first = mid + 1
    return False


if __name__ == '__main__':
    li = [17, 20, 26, 31, 44, 50, 54, 77, 93]
    result1 = binary_search(li, 20)
    print(result1)
    result2 = binary_search(li, 78)
    print(result2)

运行结果：

比较上面两种算法是运算速度：

示例代码：

from timeit import Timer


#  递归
def binary_search(li, item):
    """二分查找"""
    n = len(li)
    mid = n // 2
    if n > 0:
        if li[mid] == item:
            return True
        elif li[mid] > item:
            return binary_search(li[:mid], item)
        else:
            return binary_search(li[mid + 1:], item)
    return False


#  非递归
def binary_search2(li, item):
    """二分查找"""
    n = len(li)
    first = 0
    end = n - 1
    while first <= end:
        mid = (first + end) // 2
        if li[mid] == item:
            return True
        elif li[mid] > item:
            end = mid - 1
        else:
            first = mid + 1
    return False


if __name__ == '__main__':
    li = [17, 20, 26, 31, 44, 50, 54, 77, 93]
    print('查找成功情况下：')
    time1 = Timer('binary_search([17, 20, 26, 31, 44, 50, 54, 77, 93], 20)', 'from __main__ import binary_search')
    print('recursion running time:', time1.timeit(10))
    time2 = Timer('binary_search2([17, 20, 26, 31, 44, 50, 54, 77, 93], 20)', 'from __main__ import binary_search2')
    print('non-recursion running time:', time2.timeit(10))
    print('查找失败情况下：')
    time3 = Timer('binary_search([17, 20, 26, 31, 44, 50, 54, 77, 93], 78)', 'from __main__ import binary_search')
    print('recursion running time:', time3.timeit(10))
    time4 = Timer('binary_search2([17, 20, 26, 31, 44, 50, 54, 77, 93], 78)', 'from __main__ import binary_search2')
    print('non-recursion running time:', time4.timeit(10))

运行结果：