Python Bisect - 二叉搜尋

Harshit Jindal 2023年1月30日 2021年2月28日
  1. bisect.bisect_left() 概述
  2. bisect_left() 的應用
  3. bisect.bisect_right() 概述
  4. bisect_right() 的應用
Python Bisect - 二叉搜尋
注意
如果你想詳細瞭解二叉搜尋,那麼可以參二叉搜尋演算法一文。

在本文中,我們將看到如何使用 Python 內建模組來執行二叉搜尋。bisect 模組是基於二分法來尋找函式的根。它由 6 個函式組成。bisect()bisect_left()bisect_right()insort()insort_left()insort_right() 這 6 個函式允許我們在列表中找到元素的索引或在正確的位置插入元素。它還有助於在每次插入後保持列表的排序。但是為了使它們正常工作,我們必須確保陣列已經被排序了。

bisect.bisect_left() 概述

它用於確定一個數字 x 在排序列表中的最左邊插入點。如果列表中已經有了 x,那麼新的 x 將被插入到列表中所有 x 的最左邊位置。

語法

bisect_left(arr, x, lo = 0, hi = len(a))

引數

arr 輸入列表
x 我們要定位插入點的元素。
lo 它有助於指定一個列表子集的起始索引。預設值是 0
hi 它有助於指定一個列表子集的結束索引。預設值是 len(arr)

返回

它返回一個插入點,將陣列分成兩半:第一部分是所有小於 x 的值,第二部分是所有大於 x 的值。

bisect_left() 的應用

查詢元素的首次出現

from bisect import bisect_left 
 
def binary_search(a, x): 
    i = bisect_left(a, x) 
    if i != len(a) and a[i] == x: 
        return i 
    else: 
        return -1
 
a  = [1, 2, 3, 3, 3] 
x = int(3) 
res = binary_search(a, x) 
if res == -1: 
    print("Element not Found") 
else: 
    print("First occurrence of", x, "is at index", res)

輸出:

First occurrence of 3 is at index 2

找出小於 x 的最大值

from bisect import bisect_left 
  
def binary_search(a, x): 
    i = bisect_left(a, x) 
    if i: 
        return (i-1) 
    else: 
        return -1
  
# Driver code 
a  = [1, 2, 4, 4, 8] 
x = int(7) 
res = binary_search(a, x) 
if res == -1: 
    print("There is no value smaller than", x) 
else: 
    print("Largest value smaller than", x, " is at index", res) 

輸出:

Largest value smaller than 7 is at index 3

bisect.bisect_right() 概述

它用於返回排序列表中一個數字 x 的最右邊插入點。如果列表中已經出現了 x,那麼新的 x 將被插入到列表中所有 x 的最右邊位置。

語法

bisect_right(arr, x, lo = 0, hi = len(a))

引數

arr 輸入列表
x 我們要定位插入點的元素。
lo 它有助於指定一個列表子集的起始索引。預設值是 0
hi 它有助於指定一個列表子集的結束索引。預設值是 len(arr)

返回

它返回一個插入點,將陣列分成兩半:第一半是所有值<= x,第二半是所有值>x

bisect_right() 的應用

查詢元素的最後一次出現

from bisect import bisect_right 
  
def binary_search(a, x): 
    i = bisect_right(a, x) 
    if i != len(a)+1 and a[i-1] == x: 
        return (i-1) 
    else: 
        return -1
  
a  = [1, 2, 4, 4] 
x = int(4) 
res = binary_search(a, x) 
if res == -1: 
    print(x, "is absent") 
else: 
    print("Last occurrence of", x, "is present at", res) 

輸出:

Last occurrence of 4 is present at 3
Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

相關文章 - Python Algorithm