二分查找

目标值区间左侧

目标值区间右侧

插入【可不学】

目标值区间左侧

目标值区间右侧

参考

---

简介

方法

二分查找

目标值区间左侧

bisect_left(a, x, lo=0, hi=len(a))

在 a 中找到 x 合适的插入点以维持有序。参数 lo 和 hi 可以被用于确定需要考虑的子集；默认情况下整个列表都会被使用。如果 x 已经在 a 里存在，那么插入点会在已存在元素之前（也就是左边）。如果 a 是列表（list）的话，返回值是可以被放在 list.insert(index,object) 的第一个参数的。

返回的插入点 i 可以将数组 a 分成两部分。左侧是 all(val **<** x for val in a[lo:i]) ，右侧是 all(val **>=** x for val in a[i:hi]) 。

from bisect import *
lst = [1,2,2,5]
bisect_left(lst,4)
3
lst[:3]
[1, 2, 2]
lst[3:]
[5]

对于列表lst来说，以bisect_left返回的index为界限，lst[:index]为小于x的，lst[index:]为大于或等于x的。

lst.insert(bisect_left(lst,4),4)
lst[3]
4

使用insert方法插入x后，x就是在bisect_left返回的那个索引位置

源代码

def bisect_left(a, x, lo=0, hi=None):
    """Return the index where to insert item x in list a, assuming a is sorted.

    The return value i is such that all e in a[:i] have e < x, and all e in
    a[i:] have e >= x.  So if x already appears in the list, a.insert(x) will
    insert just before the leftmost x already there.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x: lo = mid+1
        else: hi = mid
    return lo

注意，源代码使用的是(lo+hi)//2，如果使用模块刷题时超时（Python自动转为大数运算，时间过长），可自己写个二分查找，改为lo+(hi-lo)//2。

目标值区间右侧

bisect.bisect_right(a, x, lo=0, hi=len(a))

bisect.bisect(a, x, lo=0, hi=len(a))

类似于bisect_left(a, x, lo=0, hi=len(a))，但是返回的插入点是 a 中已存在元素 x 的右侧。

返回的插入点 i 可以将数组 a 分成两部分。左侧是 all(val **<=** x for val in a[lo:i])，右侧是 all(val **>** x for val in a[i:hi]) 。

bisect_right(lst,4)
4
lst[:4]
[1, 2, 2, 4]
lst[4:]
[5]

对于列表lst来说，以bisect_left返回的index为界限，lst[:index]为小于或等于x的，lst[index:]为大于x的。

lst.insert(bisect_right(lst,4),4)
lst[4]
4

注意，已存在的4是lst[3]，新插入的4是lst[4]

插入【可不学】

给大家的福利

零基础入门

对于从来没有接触过网络安全的同学，我们帮你准备了详细的学习成长路线图。可以说是最科学最系统的学习路线，大家跟着这个大的方向学习准没问题。

同时每个成长路线对应的板块都有配套的视频提供：

因篇幅有限，仅展示部分资料

网上学习资料一大堆，但如果学到的知识不成体系，遇到问题时只是浅尝辄止，不再深入研究，那么很难做到真正的技术提升。

需要这份系统化资料的朋友，可以点击这里获取

一个人可以走的很快，但一群人才能走的更远！不论你是正从事IT行业的老鸟或是对IT行业感兴趣的新人，都欢迎加入我们的的圈子（技术交流、学习资源、职场吐槽、大厂内推、面试辅导），让我们一起学习成长！