1. 算法描述

二分法是一种效率比较高的搜索方法

回忆之前做过的猜数字的小游戏，预先给定一个小于100的正整数x，让你猜猜测过程中给予大小判断的提示，问你怎样快速地猜出来?

我们之前做的游戏给定的是10次机会，如果我们学会.二分查找法以后，不管数字是多少，最多只需要7次就能猜到数字。

2. 算法分析

1、必须是有序的序列。


2、对数据量大小有要求。


数据量太小不适合二分查找，与直接遍历相比效率提升不明显。


数据量太大也不适合用二分查找，因为数组需要连续的存储空间，若数据量太大，往往找不到存储如此大规模数据的连续内存空间。.

3. 算法思路

假设有一个有序列表如下:



请问数字11是否在此列表中，如果在它的索引值为多少?

4. 代码实现

纯算法实现

实现代码📝：

arr_list = [5, 7, 11, 22, 27, 33, 39, 52, 58]
# 需要查找的数字
seek_number = 11
# 保存一共查找了几次
count = 0
# 列表左侧索引
left = 0
# 列表右侧索引
right = len(arr_list) - 1
# 当左侧索引小于等于右侧索引时
while left <= right:
    # 取中间的索引位置
    middle = (left + right) // 2
    # 查找次数进行累加
    count += 1
    # 如果查找的数字大于中间位置的数字时
    if seek_number > arr_list[middle]:
        # 左侧索引为中间位置索引+1
        left = middle + 1
    # 如果查找的数字小于中间位置的数字时
    elif seek_number < arr_list[middle]:
        # 右侧索引为中间位置索引-1
        right = middle - 1
    # 如果等于中间索引数据
    else:
        print('数字：%s找到了，索引值为：%s' % (seek_number, middle))
        break
else:
    print("数字%s 没有找到" % seek_number)
print("一共用了：%s次查找" % count)

运行结果👇：

递归法实现

在循环中定义了一个变量count，如果第一次循环后count没有变化，就说明输入的是有序序列，这时我们直接return退出循环，这时候的时间复杂度为O(n)

实现代码📝：

arr_list = [5, 7, 11, 22, 27, 33, 39, 52, 58]


def binary_search(seek_number, left, right):
    if left <= right:
        middle = (left + right) // 2
        if seek_number < arr_list[middle]:
            right = middle - 1
        elif seek_number > arr_list[middle]:
            left = middle + 1
        else:
            return middle
        # 进行递归调用
        return binary_search(seek_number, left, right)
    # 当左侧索引大于右侧索引时，说明没有找到
    else:
        return -1


# 查找的数字
seek_number = 11
# 列表左侧索引
left = 0
# 列表右侧索引
right = len(arr_list) - 1
print("查找的数字：%s，索引为：%s" % (seek_number, binary_search(seek_number, left, right)))

运行结果👇：

《100天精通Python》专栏推荐白嫖80g Python全栈视频

《100天精通Python从入门到就业》：本专栏专门针对零基础和需要进阶提升的同学所准备的一套完整教学，从0到100的不断进阶深入，后续还有实战项目，轻松应对面试，专栏订阅地址：https://blog.csdn.net/yuan2019035055/category_11466020.html

• 优点：订阅限时9.9付费专栏进入千人全栈VIP答疑群，作者优先解答机会（代码指导、远程服务），群里大佬众多可以抱团取暖（大厂内推机会）！
• 专栏福利：简历指导、招聘内推、每周送实体书、80G全栈学习视频、300本IT电子书：Python、Java、前端、大数据、数据库、算法、爬虫、数据分析、机器学习、面试题库等等