国企有没有必要建设网站,网站最近收录,谷歌广告联盟网站,html5官网免费下载✅作者简介#xff1a;人工智能专业本科在读#xff0c;喜欢计算机与编程#xff0c;写博客记录自己的学习历程。 #x1f34e;个人主页#xff1a;小嗷犬的个人主页 #x1f34a;个人网站#xff1a;小嗷犬的技术小站 #x1f96d;个人信条#xff1a;为天地立心人工智能专业本科在读喜欢计算机与编程写博客记录自己的学习历程。 个人主页小嗷犬的个人主页 个人网站小嗷犬的技术小站 个人信条为天地立心为生民立命为往圣继绝学为万世开太平。 本文目录简介bisect 库的使用bisect_leftbisect_rightinsort_leftinsort_right二分查找基础实现简介
bisect 库是 Python 标准库中的一部分它提供了二分查找的功能。二分查找是一种在有序列表中查找某一特定元素的搜索算法。它的时间复杂度为 O(logn)O(\log n)O(logn)比顺序查找的时间复杂度 O(n)O(n)O(n) 要有效率。
bisect 库的使用
bisect 库提供了 bisect_left、bisect_right、insort_left、insort_right四个函数用于在有序列表中查找或插入元素。
bisect_left
bisect_left 函数用于在有序列表中二分查找某一位置使得在该位置插入指定元素后仍保持有序返回该位置如果元素已经存在则返回它的左边位置。
函数原型如下
bisect.bisect_left(a, x, lo0, hilen(a), *, keyNone)其中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)) # 5bisect_right
bisect_right 函数用于在有序列表中二分查找某一位置使得在该位置插入指定元素后仍保持有序返回该位置如果元素已经存在则返回它的右边位置。
函数原型如下
bisect.bisect_right(a, x, lo0, hilen(a), *, keyNone)其中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)) # 8insort_left
insort_left 函数用于在有序列表中二分查找某一位置使得在该位置插入指定元素后仍保持有序然后将元素插入该位置如果元素已经存在则插入到它的左边位置。
函数原型如下
bisect.insort_left(a, x, lo0, hilen(a), *, keyNone)其中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, lo0, hilen(a), *, keyNone)其中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 函数将元素插入到该位置。
二分查找基础实现
在 Python 中我们可以使用 bisect 库来实现二分查找但其只能根据元素的值和元素之间的比较关系来查找元素的位置如果要根据元素的其他属性或其他关系来查找元素的位置就需要自己实现二分查找了。
二分查找的基本模板如下
def binary_search(nums, target):left, right 0, len(nums) - 1while left right:mid (left right) // 2if nums[mid] target:return midelif nums[mid] target:left mid 1else:right mid - 1return -1通过修改模板我们可以根据更复杂的关系来查找元素。
示例 852. 山脉数组的峰顶索引 符合下列属性的数组 arr 称为 山脉数组 arr.length 3存在 i0 i arr.length - 1使得 arr[0] arr[1] ... arr[i-1] arr[i]arr[i] arr[i1] ... 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, 0while left right:mid (left right) // 2if arr[mid] arr[mid 1]:ans midright mid - 1else:left mid 1return ans
