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() 的应用