bisect 二分查找源码分析

Bisection.py

# coding=utf-8
"""
bisect实现源码就是**二分查找算法**，**二分查找的对象是：有序数组。这点特别需要注意。要先把数组排好序再操作。**

**基本步骤：**

- 从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；
- 如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。
- 如果在某一步骤数组为空，则代表找不到。

这种搜索算法每一次比较都使搜索范围缩小一半。时间复杂度：**O(logn)**

如下源码分析:

    :copyright: (c) 2016 by fangpeng(@beginman.cn).
    :license: MIT, see LICENSE for more details.
"""


def insort_right(a, x, lo=0, hi=None):
    """在a列表中插入元素x,且保持排序(假设a已经排过序).

    如果x已经在a中,那么插入到最右边的x的右边.
    可选参数`lo` (默认 0) and `hi` (默认 `len(a)`列表总长度) 绑定搜索的切片。
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2        # 取list中间位置
        if x < a[mid]:          # 如果x 小于list中间的值,则在前半段继续查找
            hi = mid            # hi=mid 将总长度缩短到中间
        else:                   # 如果x 大于list中间的值,则在后半段继续查找
            lo = mid+1          # lo = mid+1, 起始位置就从中间位置+1处(也就是后半段)开始
    a.insert(lo, x)