Python-二分查找算法bisect模块

一时失言乱红尘 2023-01-01 14:57 137阅读 0赞

**目录**

简介

方法

二分查找

目标值区间左侧

目标值区间右侧

插入【可不学】

目标值区间左侧

目标值区间右侧

参考

--------------------

# 简介 #

# 方法 #

## 二分查找 ##

### 目标值区间左侧 ###

**`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\]

## 插入【可不学】 ##

### 目标值区间左侧 ###

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

将 *x* 插入到一个有序序列 *a* 里，并维持其有序。如果 *a* 有序的话，这相当于 `a.insert(bisect.bisect_left(a, x, lo, hi), x)`。要注意搜索是 O(log n) 的，插入却是 O(n) 的。

注意，是insort\_left，不是insert\_left，意思是insert到一个sort后的序列。

> >>> insort\_left(lst,3)  
> >>> lst  
> \[1, 2, 2, 3, 4, 4, 5\]

源代码

def insort_left(a, x, lo=0, hi=None):
        """Insert item x in list a, and keep it sorted assuming a is sorted.
    
        If x is already in a, insert it to the left of the leftmost x.
    
        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
        a.insert(lo, x)

通过源代码发现，这就是一个二分查找和插入的过程，没必要记下来。

### 目标值区间右侧 ###

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

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

类似于`insort_left`(*a*, *x*, *lo=0*, *hi=len(a)*)，但是把 *x* 插入到 *a* 中已存在元素 *x* 的右侧。

>  >>> insort\_right(lst,3)  
> >>> lst  
> \[1, 2, 2, 3, 3, 4, 4, 5\]

注：看源代码发现真的没有性能提升，里面就是调用的insert，可以不学插入这两个函数。

# 参考 #

[python-数组二分查找算法][python-]

更多python相关内容：[【python总结】python学习框架梳理][python_python]

本人b站账号:[lady\_killer9][lady_killer9]

有问题请下方评论，转载请注明出处，并附有原文链接，谢谢！如有侵权，请及时联系。如果您感觉有所收获，自愿打赏，可选择支付宝18833895206（小于），您的支持是我不断更新的动力。

[python-]: https://docs.python.org/zh-cn/3.7/library/bisect.html
[python_python]: https://blog.csdn.net/lady_killer9/article/details/108763489
[lady_killer9]: https://space.bilibili.com/374432302