資料結構
網路
關係型資料庫管理系統
作業系統
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python 中的二分查詢（bisect）
在這裡，我們將看到 Python 中的 bisect。bisect 用於二分查詢。二分查詢技術用於查詢排序列表中的元素。bisect 是一個庫函式。
我們將看到 Python 中使用 bisect 的三種不同任務。
查詢元素的第一次出現
此 bisect.bisect_left(a, x, lo = 0, hi = len(a)) 函式用於返回 x 在已排序列表中的最左插入點。後兩個引數在此情況下是可選的。這兩個引數用於在子列表中進行搜尋。
示例
from bisect import bisect_left
def BinSearch(a, x):
i = bisect_left(a, x)
if i != len(a) and a[i] == x:
return i
else:
return -1
a = [2, 3, 4, 4, 5, 8, 12, 36, 36, 36, 85, 89, 96]
x = int(4)
pos = BinSearch(a, x)
if pos == -1:
print(x, "is absent")
else:
print("First occurrence of", x, "is at position", pos)輸出
First occurrence of 4 is at position 2
查詢小於 x 的最大值
使用 bisect_left 選項，我們可以得到大於 x (關鍵字) 的最大值。
示例
from bisect import bisect_left
def BinSearch(a, x):
i = bisect_left(a, x)
if i :
return i-1
else:
return -1
a = [2, 3, 4, 4, 5, 8, 12, 36, 36, 36, 85, 89, 96]
x = int(8)
pos = BinSearch(a, x)
if pos == -1:
print(x, "is absent")
else:
print("Larger value, smaller than", x, "is at position", pos)輸出
Larger value, smaller than 8 is at position 4
查詢 x 的最右側出現
此 bisect.bisect_right(a, x, lo = 0, hi = len(a)) 函式用於返回 x 在已排序列表中的最右插入點。後兩個引數在此情況下是可選的。這兩個引數用於在子列表中進行搜尋。
示例
from bisect import bisect_right
def BinSearch(a, x):
i = bisect_right(a, x)
if i != len(a) + 1 and a[i-1] == x:
return i-1
else:
return -1
a = [2, 3, 4, 4, 5, 8, 12, 36, 36, 36, 85, 89, 96]
x = int(36)
pos = BinSearch(a, x)
if pos == -1:
print(x, "is absent")
else:
print("Right most occurrence of", x, "is at position", pos)輸出
Right most occurrence of 36 is at position 9
更新於：2020 年 7 月 2 日
1K+ 次檢視
廣告