Python Bisect - 二叉搜尋

Harshit Jindal 2023年1月30日 2021年2月28日

Python Python Algorithm

bisect.bisect_left() 概述
bisect_left() 的應用
bisect.bisect_right() 概述
bisect_right() 的應用

注意

如果你想詳細瞭解二叉搜尋，那麼可以參二叉搜尋演算法一文。

在本文中，我們將看到如何使用 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

Author: Harshit Jindal

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.

bisect.bisect_left() 概述

語法

引數

返回

bisect_left() 的應用