二分查找

定义

一种算法，输入是一个有序的元素列表，如果查找的元素包含在列表中，则二分查找返回其位置，否则返回null；

算法实现

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @version : 1.0
# @Time    : 2019-10-26 9:47
# @Author  : cunyu
# @Email   : cunyu1024@foxmail.com
# @Site    : https://cunyu1943.github.io
# @File    : binay_search.py
# @Software: PyCharm
# @Desc    : 二分查找

# 二分查找，其中list必须为有序列表
# list是要查找的数组，item是要查找的元素
def binary_search(list, item):
    # 起始位置初始化列表为第一个元素
    low = 0
    # 终止位置为列表最后一个元素
    high = len(list) - 1
    # 循环到范围只包含一个元素
    while low <= high:
        mid = (low + high) // 2
        guess = list[mid]
        # 若找到需要查找的元素
        if guess == item:
            return mid
        # 若猜的数字大于查找的元素
        elif guess > item:
            high = mid - 1
        # 若猜的数字小于查找的元素
        else:
            low = mid + 1;
    # 若未找到指定元素
    return None


if __name__ == '__main__':
    my_list = [3, 4, 8, 11, 13, 20]
    item = int(input('输入你要查找的元素
'))
    print('元素 ' + str(item) + ' 的索引位置(从0开始)：')
    print(binary_search(my_list, item))

练习

1. 一个含有128个元素的有序列表，使用二分查找查找某元素，最多需要几步？

，所以最多需要7步就可以找到指定元素；

1. 1中列表长度翻倍后，最多需几步？

翻倍后，，所以最多需要8步；

运行时间

• 线性时间（linear time）：所需时间与查询列表长度成线性关系，则成为线性时间；
• 对数时间（log time）

大表示法

一种特殊表示法，指出算法速度；

常见大运行时间

• ：对数时间，如二分查找；
• ：线性时间，如简单查找；
• ：如快速排序；
• ：如选择排序；
• ！：如旅行商问题；

总结

• 算法速度并非时间，而是操作数的增速；
• 算法运行时间用大表示法表示；
• 快于，当搜索元素较多时，前者比后者快得多；