专栏首页Bingo的深度学习杂货店二分查找及其变形与Python的bisect模块的关系

二分查找及其变形与Python的bisect模块的关系

首先,我们完成了二分查找及其变形的 3 个函数的模板:

1、binsearch(nums, target):标准的二分查找,找不到返回-1; 2、lowerbound(nums, target):查找第一个>=target的元素索引,找不到返回数组长度; 3、upperbound(nums, target):查找第一个>target的元素索引,找不到返回数组长度。

class BinarySearch:

    # 标准的二分查找,找不到返回-1
    def binsearch(nums, target):
        lo, hi = 0, len(nums) - 1
        while lo <= hi:
            mid = lo + (hi - lo) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                hi = mid - 1
            else:  # nums[mid] < target:
                lo = mid + 1
        return -1

    # 查找第一个>=target的元素索引,找不到返回数组长度
    def lowerbound(nums, target):
        lo, hi = 0, len(nums) - 1
        pos = len(nums)  # 找不到
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if nums[mid] >= target:
                hi = mid
            else:  # nums[mid] < target:
                lo = mid + 1
        if nums[lo] >= target: # lo就是要找的元素索引
            pos = lo
        return pos

    # 查找第一个>target的元素索引,找不到返回数组长度
    def upperbound(nums, target):
        lo, hi = 0, len(nums) - 1
        pos = len(nums)  # 找不到
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if nums[mid] > target:
                hi = mid
            else:  # nums[mid] <= target:
                lo = mid + 1
        if nums[lo] > target: # lo就是要找的元素索引
            pos = lo
        return pos

然后,我们介绍 Python 的 bisect 模块(import bisect):

先说明的是,使用这个模块的函数前先确保操作的列表是已排序的。

  • 有 3 个函数:bisect.bisect(list, val)bisect.bisect_left(list, val)bisect.bisect_right(list, val),功能是在有序数组 list 中返回 val 插入位置的索引(不改变 list 本身),后两者适合包含重复元素的情况。实际上,bisect.bisect(list, val) 等价于 bisect.bisect_right(list, val)
import bisect
a = [1,1,2,2,2,2,3,4,4,5,5,6,6,6]
print(bisect.bisect(a, 0))  # 1
print(bisect.bisect_left(a, 6))  # 11
print(bisect.bisect_right(a, 2))  # 6
  • 有 3 个函数:bisect.insort(list, val)bisect.insort_left(list, val)bisect.insort_right(list, val),功能是在有序数组 list 中插入 val (会改变 list 本身)。单纯看其结果的话,3 个函数的操作结果是一样的,其实插入的位置不同而已。
import bisect
a = [1,1,2,2,2,2,3,4,4,5,5,6,6,6]
bisect.bisect(a, 0)  # a = [0,1,1,2,2,2,2,3,4,4,5,5,6,6,6]
bisect.bisect_left(a, 6)  # a = [0,1,1,2,2,2,2,3,4,4,5,5,6,6,6,6]
bisect.bisect_right(a, 2)  # a = [0,1,1,2,2,2,2,2,3,4,4,5,5,6,6,6,6]

二分查找的变形与 bisect 模块的关系:

1、二分查找中的 lowerbound(nums, target) 函数等价于 bisect.bisect_left(list, val); 2、二分查找中的 upperbound(nums, target) 函数等价于 bisect.bisect_right(list, val)bisect.bisect(list, val)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python Algorithms - C6 Divide and Combine and Conquer

    Python算法设计篇(6) Chapter 6: Divide and Combine and Conquer

    宅男潇涧
  • 不使用 if-elif 语句,如何优雅地判断某个数字所属的等级?

    题目大意是:有从 A 到 F 的 5 个等级,现要判断某个数值(从 0 到 1 之间)所属的等级。举例,如数值 >= 0.9,则属于 A;若数值 >= 0.8,...

    青南
  • 不使用 if-elif 语句,如何优雅地判断某个数字所属的等级?

    题目大意是:有从 A 到 F 的 5 个等级,现要判断某个数值(从 0 到 1 之间)所属的等级。举例,如数值 >= 0.9,则属于 A;若数值 >= 0.8,...

    Python猫
  • Python中bisect的用法及示例详解

    使用bisect.insort,比bisect先查找该插入哪个位置,再用insert方法插入更加快速的方法

    砸漏
  • 再也不担心用不好二分法了,因为我找到了"作弊"的接口

    导读:算法是程序的灵魂,而复杂度则是算法的核心指标之一。为了降低复杂度量级,可谓是令无数程序员绞尽脑汁、甚至是摧枯秀发。一般而言,若能实现对数阶的时间复杂度,算...

    luanhz
  • 《python高级编程》异常、字典、集合等

    with语句后面的as得到的是是__enter__方法的返回值, 如果__enter__返回1, 那么sample就等于1.

    乐说科技
  • Python笔记:bisect库简介

    今天在做题的时候偶然发现python中有一个强大的内置库,即bisect库,它能够轻易地实现顺序列表中的二分查找与插入操作。

    codename_cys
  • python: bisect库

    JNingWei
  • python数组二分查找算法bisect

    摘自官方文档:https://docs.python.org/zh-cn/3.7/library/bisect.html

    西西嘛呦
  • 【数据分析从入门到“入坑“系列】利用Python学习数据分析-Python数据结构-1

    元组是一个固定长度,不可改变的Python序列对象。创建元组的最简单方式,是用逗号分隔一列值:

    天道Vax的时间宝藏
  • 【利用Python进行数据分析】3-Python的数据结构、函数和文件

    元组是一个固定长度,不可改变的Python序列对象,创建元组的最简单方式,是用逗号分隔一列值。当用复杂的表达式定义元组,最好将值放到圆括号内。

    用户7886150
  • Python bisect模块原理及常见实例

    1. bisect模块为内置标准库,它实现了二分法查找算法(只要提到二分法查找,应该优先想到此模块)

    砸漏
  • 剑指offer【50~59】

    排序数组,很明显二分查找,找到第一个 >= k 的元素索引以及第一个 > k 的元素索引,两者相减即为答案,即 lowerBound - upperBound。...

    echobingo
  • Git Pro深入浅出(二)

    SHA-1 的前几个字符就可以获得对应的那次提交,当然你提供的 SHA-1 字符数量不得少于4个,并且没有歧义——也就是说,当前仓库中只有一个对象以这段 SHA...

    奋飛
  • 超全汇总!200 多个 Python 标准库介绍

    今天给大家介绍一下200多个Python标准库,让大家对Python标准库有一个大致的认识。

    sergiojune
  • Python第八周 学习笔记(1)

    bisect.bisect_left(a, x, lo=0, hi=len(a)) 查找在有序列表a中插入x的index,lo和hi用于指定列表的区间,默认是...

    py3study
  • Python 代码性能优化技巧

    众所周知,程序的性能好坏影响着用户体验。所以性能是留住用户很重要的一环。Python 语言虽然能做很多事情,但是有一个不足之处,那就是执行效率和性能不够理想。

    猴哥yuri
  • python 标准库大全

    郭楷丰
  • Python 200个标准库汇总!

    dummy_threading:threading模块的替代(当_thread不可用时)

    double

扫码关注云+社区

领取腾讯云代金券