Python Bisect - 二叉搜尋

Harshit Jindal 2023年1月30日

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

作者： 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() 的應用