Python 二分查找之bisect庫的使用詳解
簡介
bisect
庫是 Python 標準庫中的一部分,它提供瞭二分查找的功能。二分查找是一種在有序列表中查找某一特定元素的搜索算法。它的時間復雜度為 O ( log n ) 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, 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
函數將元素插入到該位置。
二分查找基礎實現
在 Python 中,我們可以使用 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庫使用內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!
推薦閱讀:
- C++實現LeetCode(34.在有序數組中查找元素的第一個和最後一個位置)
- Python3二分查找庫函數bisect(),bisect_left()和bisect_right()的區別
- Go語言題解LeetCode35搜索插入位置示例詳解
- 詳解Java中二分法的基本思路和實現
- C++實現LeetCode(33.在旋轉有序數組中搜索)