bisect_funbisect

基本信息

文件：bisect.py
属性：[’__builtins__’,
‘__cached__’,
‘__doc__’,
‘__file__’,
‘__loader__’,
‘__name__’,
‘__package__’,
‘__spec__’,
‘bisect’,
‘bisect_left’,
‘bisect_right’,
‘insort’,
‘insort_left’,
‘insort_right’]
作用：对有序数组进行插入查询处理，可插入也可不插入返回插入的索引位置
原理：二分法查询
别名：bisect等价于bisect_right,insort等价于insort_right

应用示例

• 只返回插入索引位置，不插入
  • bisect.bisect 返回插入的索引位置，重复数值默认返回右边位置
    
  • 指定处理重复数值方式
    • bisect.bisect_left 若重复，返回左边位置
    • bisect.bisect_right 若重复，返回右边位置
      
• 插入数值
  • bisect.insort 插入数，重复的默认插入右边位置
    
    结果看不出重复数值插入哪边，其实是对应disect，默认右边位置
  • 指定处理重复数值方式
    • bisect.insort_left 若重复，插入到左边位置
    • bisect.insort_right 若重复，插入到右边位置
      
      两个函数的操作结果是一样的，然而其插入的位置不同，对应disect_left和disect_right

源码解析

两者的区别在于判断条件时，等号放哪一边
$$\begin{gathered} ifa[mid]<x:lo=mid+1left \\ ifa[mid]\le x:lo=mdi+1right \end{gathered}$$
另外，入参可以指定区间【lo,hi】