python中的bisect模塊與二分查找詳情
1.bisect模塊概述
bisect是python的內(nèi)置模塊, 用于有序序列的插入和查找。 插入的數(shù)據(jù)不會(huì)影響列表的排序, 但是原有列表需要是有序的, 并且不能是倒序.
Bisect模塊提供的函數(shù)有:
- bisect.bisect_left(a,x, lo=0, hi=len(a))
- bisect.bisect_right(a,x, lo=0, hi=len(a))
- bisect.bisect(a, x,lo=0, hi=len(a))
- bisect.insort_left(a,x, lo=0, hi=len(a))
- bisect.insort_right(a,x, lo=0, hi=len(a))
- bisect.insort(a, x,lo=0, hi=len(a))
2.bisect模塊的函數(shù)詳解
2.1 bisect.bisect*()方法
- bisect.bisect_left(a,x,lo=0,hi=len(a),*,key=None)
在有序數(shù)組a中[lo,hi]區(qū)間內(nèi)查找x插入的位置,返回的是索引值。如果a中有跟x相同的元素,則x插入的位置是左邊,key指定了一個(gè)單參數(shù)的方法,該方法的返回值作為與k比較的基準(zhǔn)。
值得注意的是,key參數(shù)是3.10版本以后才添加的功能
- bisect.bisect_right(a,x,lo=0,hi=len(a),*,key=None),在有序數(shù)組a中[lo,hi]區(qū)間內(nèi)查找x插入的位置,返回索引值。如果a中有跟x相同的元素,則x插入的位置是右邊。
- bisect.bisect(a,x,lo=0,hi=len(a),*,key=None),同bisect_right
# bisect_left Vs. bisect (bisect_right) import bisect nums = [1, 2, 2, 4] i, j = bisect.bisect_left(nums, 2), bisect.bisect(nums, 2) print(i) # 輸出1 print(j) # 輸出3
可見(jiàn),針對(duì)上面給出的數(shù)組,想要插入2,使用bisect_left返回的索引值是1,使用bisect(bisect_right)返回的索引值是3。如果指定了lo和hi的話(huà),那么返回的就是在這個(gè)范圍內(nèi)的索引。如下面的例子所示。
# 指定lo和hi import bisect nums = [1, 2, 2, 2, 2, 4] i = bisect.bisect_left(nums, 2, 3) print(i) # 輸出為3
如果不指定lo=3的話(huà),返回的索引應(yīng)該是1。指定lo=3后,返回的索引為3。
關(guān)鍵字key指定了一個(gè)方法,這個(gè)方法會(huì)接受當(dāng)前數(shù)組中的中間值mid(因?yàn)槎植檎揖褪菑闹虚g值開(kāi)始的)作為其參數(shù),然后返回一個(gè)值val,val用于跟x比較。
# 指定key值 import bisect nums = [1, 2, 3, 4, 6, 8] def divide(mid): print('mid: ' + str(mid)) return mid // 2 i = bisect.bisect_left(nums, 5, key=divide) print(i)
上面的例子中定義了一個(gè)divide方法。那么bisect_left方法的執(zhí)行順序是這樣的:
- nums中的中間值mid=4, divide(mid)方法返回值為2
- 5>2,則查找nums的右子數(shù)組,即[6,8]
- [6,8]的中間值是mid=8, divide(mid)方法返回值為4
- 5>4,則繼續(xù)查找右子數(shù)組,可是已經(jīng)沒(méi)有右子數(shù)組了,則返回索引值為6.
2.2 bisect.insort*()方法
- bisect.insort_left(a,x,lo=0,hi=len(a),*,key=None),在有序數(shù)組a中[lo,hi]區(qū)間內(nèi)查找x插入的位置,返回的是索引值。如果a中有跟x相同的元素,則x插入的位置是最左邊,key指定了一個(gè)單參數(shù)的方法,該方法的返回值作為與k比較的基準(zhǔn)。
- bisect.insort_right(a,x,lo=0,hi=len(a),*,key=None),在有序數(shù)組a中[lo,hi]區(qū)間內(nèi)查找x插入的位置,返回索引值。如果a中有跟x相同的元素,則x插入的位置是最右邊。
- bisect.insort(a,x,lo=0,hi=len(a),*,key=None),同insort_right。
# bisect.insort_left import bisect nums = [1, 2, 3, 4, 6, 8] bisect.insort_left(nums, 5) print(nums) # [1, 2, 3, 4, 5, 6, 8]
值得注意的是,insort方法中的key和bisect方法中的key指定的方法針對(duì)的對(duì)象是不同的。
# bisect.insort_left with key import bisect nums = [1, 2, 3, 4, 6, 8] def divide(mid): print('mid: ' + str(mid)) return mid // 2 bisect.insort_left(nums, 5, key=divide)
可見(jiàn),key指定的方法的參數(shù)是針對(duì)x的。也就是說(shuō)insort_left方法的執(zhí)行順序是這樣的:
- mid=x=5,返回的值是2,也就是divide(x)
- mid是數(shù)組的中間值,即mid=4, divide方法返回的值是2
- divide(x)==2,則查找左子數(shù)組
- 中間值為2,mid=2, divide方法返回的值是1
- divide(x)>1,則查找右子數(shù)組
- 中間值為3,mid=3, divide方法的返回值是1
- divide(x)>1,則查找右子數(shù)組
- 沒(méi)有右子數(shù)組了,則插入位置的索引為3,得到了插入5之后的數(shù)組為[1,2,3,5,4,6,8]
3.python中的二分查找
3.1 標(biāo)準(zhǔn)的二分查找
class BinarySearch: # 標(biāo)準(zhǔn)的二分查找,找不到返回-1 def binsearch(self, nums, target): lo, hi = 0, len(nums) - 1 while lo <= hi: mid = lo + (hi - lo) // 2 if nums[mid] == target: return mid elif nums[mid] > target: hi = mid - 1 else: # nums[mid] < target: lo = mid + 1 return -1
3.2 查找第一個(gè)>=target的元素索引
class BinarySearch: # 查找第一個(gè)>=target的元素索引,找不到返回?cái)?shù)組長(zhǎng)度 def lowerbound(self, nums, target): lo, hi = 0, len(nums) - 1 pos = len(nums) # 找不到 while lo < hi: mid = lo + (hi - lo) // 2 if nums[mid] >= target: hi = mid else: # nums[mid] < target: lo = mid + 1 if nums[lo] >= target: # lo:要找的元素索引 pos = lo return pos
3.3 查找第一個(gè)>target的元素索引
class BinarySearch: # 查找第一個(gè)>target的元素索引,找不到返回?cái)?shù)組長(zhǎng)度 def upperbound(self, nums, target): lo, hi = 0, len(nums) - 1 pos = len(nums) # 找不到 while lo < hi: mid = lo + (hi - lo) // 2 if nums[mid] > target: hi = mid else: # nums[mid] <= target: lo = mid + 1 if nums[lo] > target: # lo:要找的元素索引 pos = lo return pos
4.二分查找的變形與 bisect 模塊的關(guān)系
- 二分查找中的
lowerbound(nums, target)
等價(jià)于bisect.bisect_left(a,x, lo=0, hi=len(a))
- 二分查找中的
upperbound(nums, target)
等價(jià)于bisect.bisect_right(a,x, lo=0, hi=len(a))
或者bisect.bisect(a,x, lo=0, hi=len(a))
到此這篇關(guān)于python中的bisect模塊與二分查找詳情的文章就介紹到這了,更多相關(guān)python bisect模塊 內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Python游戲開(kāi)發(fā)實(shí)例之graphics實(shí)現(xiàn)AI五子棋
五子棋是經(jīng)典的棋牌類(lèi)游戲,很多人都玩過(guò),那么如何用Python實(shí)現(xiàn)五子棋呢,文中通過(guò)示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-11-11基于keras中的回調(diào)函數(shù)用法說(shuō)明
這篇文章主要介紹了基于keras中的回調(diào)函數(shù)用法說(shuō)明,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2020-06-06在Django中編寫(xiě)模版節(jié)點(diǎn)及注冊(cè)標(biāo)簽的方法
這篇文章主要介紹了在Django中編寫(xiě)模版節(jié)點(diǎn)及注冊(cè)標(biāo)簽的方法,Django是Python各式各樣的高人氣框架中最為著名的一個(gè),需要的朋友可以參考下2015-07-07玩轉(zhuǎn)python爬蟲(chóng)之URLError異常處理
這篇文章主要介紹了python爬蟲(chóng)的URLError異常處理,詳細(xì)探尋一下URL\HTTP異常處理的相關(guān)內(nèi)容,通過(guò)一些具體的實(shí)例來(lái)分析一下,非常的簡(jiǎn)單,但是卻很實(shí)用,感興趣的小伙伴們可以參考一下2016-02-02python代碼實(shí)現(xiàn)小程序登錄流程時(shí)序總結(jié)
這篇文章主要為大家介紹了python代碼實(shí)現(xiàn)小程序的登錄案例,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步早日升職加薪2022-04-04Python基于隨機(jī)采樣一至性實(shí)現(xiàn)擬合橢圓(優(yōu)化版)
這篇文章主要對(duì)上一版的Python基于隨機(jī)采樣一至性實(shí)現(xiàn)擬合橢圓的優(yōu)化,文中的示例代碼講解詳細(xì),具有一定的借鑒價(jià)值,感興趣的可以了解一下2022-11-11Python操控mysql批量插入數(shù)據(jù)的實(shí)現(xiàn)方法
這篇文章主要介紹了Python操控mysql批量插入數(shù)據(jù)的實(shí)現(xiàn)方法,本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-10-10簡(jiǎn)單的連接MySQL與Python的Bottle框架的方法
這篇文章主要介紹了簡(jiǎn)單的連接MySQL與Python的Bottle框架的方法,主要基于mysql-connector插件,需要的朋友可以參考下2015-04-04