Python3二分查找庫函數bisect(),bisect_left()和bisect_right()的區別

Posted on by

前提：列表有序！！！

bisect()和bisect_right()等同，那下面就介紹bisect_left()和bisec_right()的區別！

用法：

index1 = bisect(ls, x)   #第1個參數是列表，第2個參數是要查找的數，返回值為索引
index2 = bisect_left(ls, x)
index3 = bisec_right(ls, x)

bisect.bisect和bisect.bisect_right返回大於x的第一個下標(相當於C++中的upper_bound)，bisect.bisect_left返回大於等於x的第一個下標(相當於C++中的lower_bound)。

case 1

如果列表中沒有元素x，那麼bisect_left(ls, x)和bisec_right(ls, x)返回相同的值，該值是x在ls中“合適的插入點索引，使得數組有序”。此時，ls[index2] > x，ls[index3] > x。

import bisect
ls = [1,5,9,13,17]
index1 = bisect.bisect(ls,7)
index2 = bisect.bisect_left(ls,7)
index3 = bisect.bisect_right(ls,7)
print("index1 = {}, index2 = {}, index3 = {}".format(index1, index2, index3))

程序運行結果為，

index1 = 2, index2 = 2, index3 = 2

case 2

如果列表中隻有一個元素等於x，那麼bisect_left(ls, x)的值是x在ls中的索引，ls[index2] = x。而bisec_right(ls, x)的值是x在ls中的索引加1，ls[index3] > x。

import bisect
ls = [1,5,9,13,17]
index1 = bisect.bisect(ls,9)
index2 = bisect.bisect_left(ls,9)
index3 = bisect.bisect_right(ls,9)
print("index1 = {}, index2 = {}, index3 = {}".format(index1, index2, index3))

程序運行結果為，

index1 = 3, index2 = 2, index3 = 3

case 3

如果列表中存在多個元素等於x，那麼bisect_left(ls, x)返回最左邊的那個索引，此時ls[index2] = x。bisect_right(ls, x)返回最右邊的那個索引加1，此時ls[index3] > x。

import bisect
ls = [1,5,5,5,17]
index1 = bisect.bisect(ls,5)
index2 = bisect.bisect_left(ls,5)
index3 = bisect.bisect_right(ls,5)
print("index1 = {}, index2 = {}, index3 = {}".format(index1, index2, index3))

程序運行結果為，

index1 = 4, index2 = 1, index3 = 4

到此這篇關於Python3二分查找庫函數bisect(), bisect_left()和bisect_right()介紹的文章就介紹到這瞭,更多相關Python3二分查找庫函數bisect()內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：