1. 前提

二分法查询，要求目标集合必须是有序的，无序集合需要先进行排序。 二分法查询的原理一言蔽之“一次缩小一半的搜索范围”。

理解算法原理和掌握算法是不一样的，动手实现才是最终的检验标准。

一起逐步实现一个二分法查找函数 binary_search 吧。 二分法查找需要两个参数：

• 目标数组，命名为 theList，不能叫 list，会与 python 内置的 list 命名冲突。
• 要查找的值，命名为 target。

2. 一轮查找

基于循环的二分法查找，实际上是不断的调用这样的过程：确认查找范围中点与目标值之间的关系。实现二分法查找的第一步，实现一个简单的功能，确定目标值 target 与 查找范围中点 mid 之间的关系是下面哪一种：

• target == mid
• target 在 mid 左侧
• target 在 mid 右侧

当然，如果查找范围中已经没有内容可查，就意味着数组中不存在 target，这个特殊的边界条件，决定的是循环何时结束，我们最后再讨论。

2.1 初始化

首先我们指定查找范围，从 left 开始，到 right（包含）结束。
最开始查找范围当然是整个数组，特别注意，数组的最大索引是 len - 1

lenth = len(theList)
left = 0
right = length - 1

2.2 计算中点索引

计算中点的索引 midIndex。一种比较自然的方式是: left + (right - left)/2 或者采用下面的方式，注意 python 里的除法结果是浮点数，也就是浮点数，就算小数部分为 0， 结果也是浮点数，比如 2.0。使用 int() 将 (left + right)/2 转化为整数，采用的是向下取整————直接丢弃小数部分。

midIndex = int((left + right)/2)

找到中点索引 midIndex 的目标是访问 mid 的值。

2.3 当中点就是目标值 target 的情况

为了后面编写代码方便，我们把 midIndex 位置的值保存在 midValue 中。

如果目标 target 与 midValue 相等，也就是找到了目标，函数直接返回中间点的索引 midIndex 就可以退出函数了。

midValue = theList[midIndex]
if midValue == target:
    return midIndex

2.4 当目标值大于中间值

也就是说，目标值 target 在中间值右侧部分。 直接调整 left 到中间索引的下一个位置，下一轮就可以在中间点右侧区域查找 target 了。

if target > midValue:
    left = midIndex + 1
    # 跳转到 2.2 步骤

然后要开始下一轮循环。 可能会用到 continue，这样就可以不用 elif 语句了，完整代码中有演示。

2.5 当目标值小于中间值

即目标值 target 在中间值左侧部分。类似上一种情况，直接调整 right 到中间索引的前一位置，下一轮查找就会在中间点左侧区域查找 target 了。

if target < midValue:
    right = midIndex - 1
    # 跳转到 2.2 步骤

我们同样需要进入下一轮搜索，但是因为这是最后一种情况了，即使什么都不做，代码也会进入下一轮循环。

3. 终止条件

循环结束的可能有两种：

• 找到 target，返回 target 的索引
• 里里外外都找了，但是就是没有 target， 返回 None

第一种情况，在 2.3 步骤已经实现了。

第二种情况，需要在循环控制条件中实现。

可以想象， 从 left --> right 是搜索范围，left 不断的向右移动， right 不断向左移动， 如果一直找不到 target，最终 left 会跑到 right 右侧，也就意味着已经没有可以查找区间了，就应当结束循环。

# 只要 left 没有跑到 right 右侧，就继续下一轮查找
while right >= left:
    # loop

4. 完整代码

# theList 是要查找的列表
# target 是要查找的元素
# 如果在 theList 中找到 target 值，返回target所在的索引
# 没找到则返回 None
def binary_search(theList, target):
    # 设置初始检索范围， 0 ～ 最大索引， 初始化检索区域左侧索引 left 为 0，从头开始检索
    left = 0
    # 初始化检索区域右侧索引 right 为 theList 的最大索引，也就是 len(theList) - 1
    right = len(theList) - 1


    # 只要 右侧索引大于等于左侧索引，也就是检索区域还有宽度，就执行循环
    while right >= left:
        # 计算区域中间元素的索引，保存在 minIndex 变量
        midIndex = int((left + right)/2)
        # 读取 theList 中间索引对应的值 到 mid 变量
        mid = theList[midIndex]

        # 如果 target 等于目标值，找到目标
        if mid == target:
            # 返回中间索引
            return midIndex
        # 否则 如果 target 大于中间值，也就是目标在中间值的 右侧
        elif target > mid:
            # 更新检索区域的左侧索引为中间索引的下一位置 
            left = midIndex + 1
        # 否则，target 小于中间值，目标值在中间值的左侧
        else:
            # 更新检索区域的右侧索引为中间索引的前一位置
            right = midIndex - 1

    # 如果运行到这里，也就是没有在循环中返回，即没有找到 target，返回 None
    return None

如果能利用 continue，代码会更整洁

# theList 是要查找的列表
# target 是要查找的元素
# 如果在 theList 中找到 target 值，返回target所在的索引
# 没找到则返回 None
def binary_search(theList, target):
    # 设置初始检索范围， 0 ～ 最大索引， 初始化检索区域左侧索引 left 为 0，从头开始检索
    left = 0
    # 初始化检索区域右侧索引 right 为 theList 的最大索引，也就是 len(theList) - 1
    right = len(theList) - 1


    # 只要 右侧索引大于等于左侧索引，也就是检索区域还有宽度，就执行循环
    while right >= left:
        # 计算区域中间元素的索引，保存在 minIndex 变量
        midIndex = int((left + right)/2)
        # 读取 theList 中间索引对应的值 到 mid 变量
        mid = theList[midIndex]

        # 如果 target 等于目标值，找到目标
        if mid == target:
            # 返回中间索引
            return midIndex

        # 否则 如果 target 大于中间值，也就是目标在中间值的 右侧
        if target > mid:
            # 更新检索区域的左侧索引为中间索引的下一位置 
            left = midIndex + 1
            continue

        # 否则，target 小于中间值，目标值在中间值的左侧
        # 更新检索区域的右侧索引为中间索引的前一位置
        right = midIndex - 1

    # 如果运行到这里，也就是没有在循环中返回，即没有找到 target，返回 None
    return None

可以用下面的代码测试

# 可以用下面的list 测试自己的函数对不对
testData = [3,5,8,15,30]

#在 testData 中查找 5
index = binary_search(testData, 5)

print(index)  # 应该输出 1

#在 testData 中查找 15
index = binary_search(testData, 15)

print(index)  # 应该输出 3

#在 testData 中查找 9
index = binary_search(testData, 9)

print(index)  # 应该输出 None