bisect&pop,remove,del的区别&双指针使用场景

这篇文章有三个知识点：

• python的二分查找库bisect
• pop,remove,del的区别
• 双指针使用场景的简单说明

bisect

bisect是一种数组二分查找算法库，返回合适的插入位置索引。

参考：https://docs.python.org/zh-cn/3.6/library/bisect.html

用途

• 对有序列表提供支持，辅助进行查找，插入，排序。

常用函数【搜索与插入】

要注意搜索是 O(log n) 的，插入却是 O(n) 的（数组的插入）

搜索

在 a 中找到数字 x 合适的插入点以维持有序,当不存在和x相同的数时，下面两个方法返回的结果相同：

1. bisect.bisect_left(a, x, lo=0, hi=len(a))
   返回的插入点 i 可以将数组 a 分成两部分。左侧是 all(val < x for val in a[lo:i]) ，右侧是 all(val >= x for val in a[i:hi])
   在存在多个和x相等的数时，a[i]是第一个和x相等的数
2. bisect.bisect_right(a, x, lo=0, hi=len(a))

在存在多个和x相等的数时，a[i]是第一个不和x相等的数，左侧是小于等于x的数

    a=[1,2,2,3,4]
    print(bisect.bisect_left(a, 2)) # 1
    print(bisect.bisect_right(a, 2))# 3

插入

将 x 插入到一个有序序列 a 里，并维持其有序：

1. bisect.insort_left(a, x, lo=0, hi=len(a))
   相当于 a.insert(bisect.bisect_left(a, x, lo, hi), x)。

2. bisect.insort_right(a, x, lo=0, hi=len(a))
   相当于 a.insert(bisect.bisect_right(a, x, lo, hi), x)。

pop,remove,del的区别

在使用目的上都是为了从一个列表中移除元素

不同点	使用结果	返回数据	异常
remove	移除第一个相同的元素	不返回数据	ValueError: list.remove(x): x not in list
del	按照索引移除元素	不返回数据	IndexError: list assignment index out of range
pop	按照索引移除元素	返回被移除的元素	IndexError: pop index out of range

双指针使用场景的简单说明

1. 从两端向中间迭代数组：一个指针从头部开始，另一个指针从尾部开始。【如反转】
2. 同时有一个快指针和一个慢指针：确定两个指针的移动策略。【如原地移除一个列表中所有等于val的元素】