Python 二分查找之bisect库的使用详解

目录

简介

bisect>

bisect>

bisect 库提供了 bisect_left、bisect_right、insort_left、insort_right四个函数，用于在有序列表中查找或插入元素。

bisect_left

bisect_left>

函数原型如下：

bisect.bisect_left(a, x, lo=0, hi=len(a), *, key=None)

其中，a 是一个有序列表，x 是要查找的元素，lo 和 hi 是查找范围的左右边界，key 是一个函数，用于从列表中提取比较的键值。

示例：

# 导入 bisect 库
import bisect
# 有序列表
a = [1, 2, 3, 3, 5, 6, 6, 6, 8, 10]
# 查找元素 4 的位置
print(bisect.bisect_left(a, 4))  # 4
# 查找元素 6 的位置
print(bisect.bisect_left(a, 6))  # 5

bisect_right

bisect_right>

函数原型如下：

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

其中，a 是一个有序列表，x 是要查找的元素，lo 和 hi 是查找范围的左右边界，key 是一个函数，用于从列表中提取比较的键值。

示例：

# 导入 bisect 库
import bisect
# 有序列表
a = [1, 2, 3, 3, 5, 6, 6, 6, 8, 10]
# 查找元素 4 的位置
print(bisect.bisect_right(a, 4))  # 4
# 查找元素 6 的位置
print(bisect.bisect_right(a, 6))  # 8

除此之外，bisect_right 还可以简写为 bisect ：

# 导入 bisect 库
import bisect
# 有序列表
a = [1, 2, 3, 3, 5, 6, 6, 6, 8, 10]
# 查找元素 4 的位置
print(bisect.bisect(a, 4))  # 4
# 查找元素 6 的位置
print(bisect.bisect(a, 6))  # 8

insort_left

insort_left>

函数原型如下：

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

其中，a 是一个有序列表，x 是要插入的元素，lo 和 hi 是查找范围的左右边界，key 是一个函数，用于从列表中提取比较的键值。

示例：

# 导入 bisect 库
import bisect
# 有序列表
a = [1, 2, 3, 3, 5, 6, 6, 6, 8, 10]
# 插入元素 4
bisect.insort_left(a, 4)
print(a)  # [1, 2, 3, 3, 4, 5, 6, 6, 6, 8, 10]
# 插入元素 6
bisect.insort_left(a, 6)
print(a)  # [1, 2, 3, 3, 4, 5, 6, 6, 6, 6, 8, 10]

insort_right

insort_right>

函数原型如下：

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

其中，a 是一个有序列表，x 是要插入的元素，lo 和 hi 是查找范围的左右边界，key 是一个函数，用于从列表中提取比较的键值。

示例：

# 导入 bisect 库
import bisect
# 有序列表
a = [1, 2, 3, 3, 5, 6, 6, 6, 8, 10]
# 插入元素 4
bisect.insort_right(a, 4)
print(a)  # [1, 2, 3, 3, 4, 5, 6, 6, 6, 8, 10]
# 插入元素 6
bisect.insort_right(a, 6)
print(a)  # [1, 2, 3, 3, 4, 5, 6, 6, 6, 6, 8, 10]

除此之外，insort_right 还可以简写为 insort ：

# 导入 bisect 库
import bisect
# 有序列表
a = [1, 2, 3, 3, 5, 6, 6, 6, 8, 10]
# 插入元素 4
bisect.insort(a, 4)
print(a)  # [1, 2, 3, 3, 4, 5, 6, 6, 6, 8, 10]
# 插入元素 6
bisect.insort(a, 6)
print(a)  # [1, 2, 3, 3, 4, 5, 6, 6, 6, 6, 8, 10]

insort 函数的实质是调用 bisect 函数获取插入位置，然后调用 list.insert 函数将元素插入到该位置。

二分查找基础实现

在>bisect 库来实现二分查找，但其只能根据元素的值和元素之间的比较关系来查找元素的位置，如果要根据元素的其他属性或其他关系来查找元素的位置，就需要自己实现二分查找了。

二分查找的基本模板如下：

def binary_search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

通过修改模板，我们可以根据更复杂的关系来查找元素。

示例：

852. 山脉数组的峰顶索引
符合下列属性的数组 arr 称为 山脉数组 ：

arr.length >= 3存在 i（0 < i < arr.length - 1）使得：
arr[0] < arr[1] < ... arr[i-1] < arr[i]arr[i] > arr[i+1] > ... > arr[arr.length - 1]

给你由整数组成的山脉数组 arr ，返回任何满足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/peak-index-in-a-mountain-array

解

class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        n = len(arr)
        left, right, ans = 1, n - 2, 0
        while left <= right:
            mid = (left + right) // 2
            if arr[mid] > arr[mid + 1]:
                ans = mid
                right = mid - 1
            else:
                left = mid + 1
        return ans

到此这篇关于Python 二分查找：bisect库的使用的文章就介绍到这了,更多相关Python bisect库使用内容请搜索易采站长站以前的文章或继续浏览下面的相关文章希望大家以后多多支持易采站长站！