如何在Python中进行二分查找

5个月前 233次点击 来自 其他

收录专题: Python边学边译

标签: Python

原文链接:How to Do a Binary Search in Python

**二分查找(Binary search)**是计算机科学中的经典算法。它经常出现在编程竞赛和技术采访中。即使您了解概念,实现二分查找也不简单。除非您感到好奇或有特定任务,否则应始终利用Python现有的库。

在本教程中,您将学习如何:

  • 使用**bisect**模块在Python中进行二分查找
  • 在Python中以**递归(recursively)**和 **迭代(iteratively)**的方式实现二分查找
  • 识别并修复Python内置二分查找的缺陷
  • 分析二分查找时空复杂度
  • 更快的二分查找

本教程需要您熟悉Python内置数据类型,例如listtuples

获取测试数据

在本教程的下一部分中,您将使用Internet电影数据库(IMDb)的子集对搜索算法的性能进行基准测试。此数据集可免费用于个人和非商业用途。它作为一堆压缩的制表符分隔值(TSV)文件分发,这些文件每天更新。

教程需要使用到的文件是IMDb数据库中的name.basics.tsv.gz,其中包含演员,导演,作家等的记录。请在本地执行download_imdb.py后即可获得"names.txt"与"sorted_names.txt"文档:

import csv
import gzip
import shutil
import tempfile
import urllib.request


def main():
    """Script entry point."""

    print("Fetching data from IMDb...")

    with open("names.txt", "w", encoding="utf-8") as destination:
        destination.writelines(names())

    with open("names.txt", encoding="utf-8") as source, open(
        "sorted_names.txt", "w", encoding="utf-8"
    ) as destination:
        destination.writelines(sorted(source.readlines()))

    print('Created "names.txt" and "sorted_names.txt"')


def names():
    """Return a generator of names with a trailing newline."""
    url = "https://datasets.imdbws.com/name.basics.tsv.gz"
    with urllib.request.urlopen(url) as response:
        with tempfile.NamedTemporaryFile(mode="w+b") as archive:
            shutil.copyfileobj(response, archive)
            archive.seek(0)
            with gzip.open(archive, mode="rt", encoding="utf-8") as tsv_file:
                tsv = csv.reader(tsv_file, delimiter="\t")
                next(tsv)  # Skip the header
                for record in tsv:
                    full_name = record[1]
                    yield f"{full_name}\n"


if __name__ == "__main__":
    try:
        main()
    except KeyboardInterrupt:
        print("Aborted")

"names.txt"包含通过从原始TSV文件中删去第二列而获得的名称列表:

Fred Astaire
Lauren Bacall
Brigitte Bardot
John Belushi
Ingmar Bergman
...

"sorted_names.txt"是"names.txt"的排序版本。两个文件准备就绪后,您可以使用以下功能将它们加载到Python中:

def load_names(path):
    with open(path) as text_file:
        return text_file.read().splitlines()

names = load_names('names.txt')
sorted_names = load_names('sorted_names.txt')

请注意,.splitlines()的作用是删除字符串每行尾随的换行符。

测量执行时间

要评估特定算法的性能,您可以针对IMDb数据集测量其执行时间。通常,这是借助内置的timetimeit模块来完成。

如果需要,您还可以定义一个自定义装饰器来计时一个函数。例如使用time.perf_counter_ns(),它提供了纳秒级的高精度。

了解搜索算法

搜索无处不在,并且是计算机科学的核心。您可能仅今天就进行了几次网络搜索,但是您是否想知道搜索的真正含义?

搜索算法采用许多不同的形式。例如,您可以:

  • 全文检索(full-text search)
  • 模糊搜索(fuzzy searching)匹配字符串
  • 在图中找到最短路径
  • 查询数据库
  • 寻找最小值或最大值

随机搜寻

您如何寻找背包中的东西?您可能会把手伸进去,随机选择一个项目,然后看看它是否是您想要的。如果运气不好,则将其放回原处,冲洗并重复。随机搜索是效率最低的搜索算法之一。这种方法效率低下的原因是,您冒着多次选择相同错误物品的风险。

对于微观数据集,随机搜索算法可以相当快地完成工作:

>>> from search.random import *
>>> fruits = ['orange', 'plum', 'banana', 'apple']
>>> contains(fruits, 'banana')
True
>>> find_index(fruits, 'banana')
2
>>> find(fruits, key=len, value=4)
'plum'

但是,想象一下必须通过数百万个元素进行这样的搜索!例如,针对本例中的IMDb数据集,那么想要得到搜索结果,一切都仅凭运气。

该算法具有不确定的性能,主要反应在两个方面:

  1. 找到一个元素的平均时间不取决于其所在的位置,但最佳和最差时间相差两到三个数量级。
  2. 在具有一些重复项的元素集合中,该算法随机选择元素,因此不可避免地会在后续运行中返回不同的副本。

您如何对此进行改进?答案是线性搜索

线性搜索

实际上,如果您有一定的Python使用经验,那么您的代码中一定少不了线性搜索的使用。例如,在list数组中查找一个元素的索引:

>>> fruits = ['orange', 'plum', 'banana', 'apple']
>>> fruits.index('banana')
2
>>> fruits.index('blueberry')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: 'blueberry' is not in list

如果使用更Pythonic的方式,您可以使用 in 操作符来检查集合是否包含一个元素:

>>> 'banana' in fruits
True
>>> 'blueberry' in fruits
False

让我们使用timeit模块对这2种线性搜索进行一次测试,我们发现Python实现的index运行速度可能比in 操作符运行速度慢十倍,这是因为in 操作符是使用纯C编写实现的,可编译为本机代码,而index则不是如此:

>>> import timeit
>>> from search.linear import contains
>>> fruits = ['orange', 'plum', 'banana', 'apple']
>>> timeit.timeit(lambda: contains(fruits, 'blueberry'))
1.8904765040024358
>>> timeit.timeit(lambda: 'blueberry' in fruits)
0.22473459799948614

但是,对于足够大的数据集,即使是本机代码也将达到其极限,唯一的解决方案是重新考虑算法。

注: in操作并不总是做线性搜索。例如在set中,它会执行基于哈希的搜索。in操作支持任何可迭代的数据类型,其中包括tuplelistsetdict,和str。您甚至可以通过实现magic方法 .__contains__()来定义基础逻辑来支持自定义类。

二分查找

相信只要有一点编程经验,都必然了解过二分查找的相关知识。

二分查找有一定的算法要求:

  1. 数据采用顺序存储结构。
  2. 数据有序排列。

首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。

二分查找是**分而治之(divide-and-conquer)**技术的一个很好的例子,该技术将一个问题划分为许多同类的较小问题。然后将各个解决方案合并以形成最终答案。该技术的另一个著名示例是快速排序算法。

与其他搜索算法不同,二分查找不仅可以使用搜索,它也应用于进行集合成员资格测试,找到最大值或最小值,找到目标值的最近邻居,执行范围查询等等。

如果速度是头等大事,那么二分查找并不总是最佳选择。甚至有更快的算法可以利用基于散列的数据结构。但是,这些算法需要大量额外的内存,而二分查找提供了很好的时空权衡(space-time tradeoff)。

基于哈希的搜索(Hash-Based Search)

为了更快地搜索,您需要缩小问题空间。二分查找通过将每一步的候选对象数量减半来实现该目标。这意味着即使您拥有一百万个元素,只要所有元素都已排序,最多也需要二十次比较就能确定该元素是否存在。

最快的搜索方式是知道在哪里找到您要查找的内容。如果您知道某个元素的确切存储位置,则无需直接搜索就可以直接访问它。将元素或键(更常见的)映射到内存中的元素位置称为 哈希hashing

您可以认为哈希不是在搜索特定元素,而是根据元素本身计算索引。这就是哈希函数的工作,该哈希函数需要保留某些数学属性。一个好的哈希函数应该:

  • 取任意输入并将其转换为固定大小的输出。
  • 具有均匀的值分布以减轻哈希冲突(hash collisions)
  • 产生确定性的结果。
  • 单向函数(one-way function)。
  • 放大输入变化以达到雪崩效果(avalanche effect)。

同时,它应该只需少量算力,否则其成本将超过收益。散列函数还用于数据完整性验证以及加密中。

使用此概念将键映射到值的数据结构称为映射(map), 哈希表(hash table)字典(dictionary)关联数组(associative array)

让我们将IMDb数据集中的名称放入字典中,以便每个名称成为键,而对应的值成为其索引:

>>> from benchmark import load_names
>>> names = load_names('names.txt')
>>> index_by_name = {
...     name: index for index, name in enumerate(names)
... }

现在,检查元素的存在以及获取其索引非常简单:

>>> 'Guido van Rossum' in index_by_name
False
>>> 'Arnold Schwarzenegger' in index_by_name
True
>>> index_by_name['Arnold Schwarzenegger']
215

现在我们来比骄一下针对IMDb数据集,线性搜索与基于散列的搜索算法性能

线性搜索

搜索词 元素索引 最好的时间 平均时间 最差的时间
Fred Astaire 0 491ns 1.17µs 6.1µs
Alicia Monica 4,500,000 0.37s 0.38s 0.39s
Baoyin Liu 9,500,000 0.77s 0.79s 0.82s
missing N/A 0.79s 0.81s 0.83s

基于散列的搜索算法

搜索词 元素索引 最好的时间 平均时间 最差的时间
Fred Astaire 0 0.18µs 0.4µs 1.9µs
Alicia Monica 4,500,000 0.17µs 0.4µs 2.4µs
Baoyin Liu 9,500,000 0.17µs 0.4µs 2.6µs
missing N/A 0.19µs 0.4µs 1.7µs

通过观察,您应该很清楚基于散列的搜索算法的性能是大大优于线性搜索。同样的,如果我们进一步对比二分查找:

搜索词 元素索引 平均时间 比较次数
(…) Berendse 0 6.52µs 23
Jonathan Samuangte 4,499,997 6.99µs 24
Yorgos Rahmatoulin 9,500,001 6.5µs 23
missing N/A 7.2µs 23

可以观察到散列的搜索算法的平均时间,不仅比Python实现二分查找快一个数量级,而且无论在何处,所有元素的速度都保持不变。

那么我们为什么不直接使用散列的搜索算法,还需要在此重点讨论二分查找呢?原因就是散列的搜索算法的缺点。

散列的搜索算法基于字典,需要消耗大量的内存空间,使得算法的加载时间变慢,并且需要使其他数据与字典内容保持一致。字典在其键上施加的另一个约束是它们必须是可散列的,并且其散列值不能随时间变化。您可以通过调用以下命令来检查特定数据类型在Python中是否可哈希化hash():

>>> key = ['round', 'juicy']
>>> hash(key)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'

可变集合,例如 list, set, dict都不可哈希。实际上,字典键应该是不可变的,因为它们的哈希值通常取决于键的某些属性。如果可变集合是可哈希的并且可以用作键,则每次更改内容时其哈希值都将不同。

正如上文所讲,二分查找提供了很好的时空权衡(space-time tradeoff),故而在更多情况下,二分查找或许是更好的选择。

使用bisect模块

您可以使用Python中内置bisect模块执行二分查找,这也有助于按排序顺序保留列表。它基于二分法来查找函数的根。该模块具有六个功能,分为两个类别:

查找索引 插入元素
bisect() insort()
bisect_left() insort_left()
bisect_right() insort_right()

寻找元素

要在排序列表中找到现有元素的索引,您需要bisect_left():

>>> import bisect
>>> sorted_fruits = ['apple', 'banana', 'orange', 'plum']
>>> bisect.bisect_left(sorted_fruits, 'banana')
1

输出结果告诉您,香蕉是列表中的第二个水果,因为它是在index处找到的1。但是,如果缺少一个元素,那么您仍将获得其预期位置:

>>> bisect.bisect_left(sorted_fruits, 'apricot')
1
>>> bisect.bisect_left(sorted_fruits, 'watermelon')
4

即使这些水果不在清单上,您也可以对放置它们的位置有所了解。例如,杏子应介于苹果和香蕉之间,而西瓜应成为最后一个元素。通过评估两个条件,您将知道是否找到了一个元素:

  1. 索引是否在列表的范围内?

  2. 元素的值是所希望的吗?

可以将其转换为用于按值查找元素的通用函数:

def find_index(elements, value):
    index = bisect.bisect_left(elements, value)
    if index < len(elements) and elements[index] == value:
        return index

匹配时,该函数将返回相应的元素索引。否则,它将隐式返回None

要按键搜索,您必须维护一个单独的键列表。由于这会产生额外的费用,因此值得预先计算密钥并尽可能多地重用它们。您可以定义一个帮助程序类,以便能够通过不同的键进行搜索,而无需引入太多重复代码:

class SearchBy:
    def __init__(self, key, elements):
        self.elements_by_key = sorted([(key(x), x) for x in elements])
        self.keys = [x[0] for x in self.elements_by_key]

键是作为第一个参数传递给的函数__init__()。拥有它之后,您将创建一个键-值对的排序列表,以便以后可以从其键中检索元素。用元组表示键值对,保证了每个键值对的第一个元素都将被排序。在下一步中,您提取键以创建适合您实现的Python二分查找平面列表。

以下是按键查找元素的实际方法:

class SearchBy:
    def __init__(self, key, elements):
        self.elements_by_key = sorted([(key(x), x) for x in elements])
        self.keys = [x[0] for x in self.elements_by_key]

    def find(self, value):
        index = bisect.bisect_left(self.keys, value)
        if index < len(self.keys) and self.keys[index] == value:
            return self.elements_by_key[index][1]

此代码将已排序键的列表一分为二,以按键获取元素的索引。如果存在这样的键,则可以使用其索引从先前计算的键值对列表中获取相应的对。该对中的第二个元素是期望值。

如果您有多个香蕉,bisect_left()则将返回最左边的实例:

>>> sorted_fruits = [
...     'apple',
...     'banana', 'banana', 'banana',
...     'orange',
...     'plum'
... ]
>>> bisect.bisect_left(sorted_fruits, 'banana')
1

要获得最右边的香蕉,您需要调用bisect_right()bisect() :

>>> bisect.bisect_right(sorted_fruits, 'banana')
4
>>> bisect.bisect(sorted_fruits, 'banana')
4
>>> sorted_fruits[4]
'orange'

合并代码后,您可以看到有多少香蕉:

>>> l = bisect.bisect_left(sorted_fruits, 'banana')
>>> r = bisect.bisect_right(sorted_fruits, 'banana')
>>> r - l
3

插入新元素

bisect模块的另一个实际应用是维护已排序列表中元素的顺序

>>> import bisect
>>> sorted_fruits = ['apple', 'banana', 'orange']
>>> bisect.insort(sorted_fruits, 'apricot') >>> bisect.insort_left(sorted_fruits, 'watermelon') >>> bisect.insort_right(sorted_fruits, 'plum') >>> sorted_fruits
['apple', 'apricot', 'banana', 'orange', 'plum', 'watermelon']

在列表中没有重复项之前,您不会发现任何区别。但是即使那样,只要这些重复项是简单值,它就不会变得明显。在左侧添加(insort_left)香蕉与在右侧添加(insort_right)香蕉具有相同的效果。

为了说明这些差异,我们将设计一个数据类型,尽管其值相等,但其对象仍可以具有唯一标识。让我们使用@dataclass装饰器定义类型,它是Python 3.7中引入的:

from dataclasses import dataclass, field

@dataclass
class Person:
    name: str
    number: int = field(compare=False)

    def __repr__(self):
        return f'{self.name}({self.number})'

一个人被分配了一个name和任意一个number。把字段number从相等性测试中排除,那么即使两个人的属性值不同,也可以使两个人相等:

>>> p1 = Person('John', 1)
>>> p2 = Person('John', 2)
>>> p1 == p2
True

另一方面,这两个变量引用完全独立的实体,这使您可以区分它们:

>>> p1 is p2
False
>>> p1
John(1)
>>> p2
John(2)

变量p1和p2确实是不同的对象。

请注意,默认情况下,数据类实例是不可比较的,这将阻止您对它们使用bisect算法:

>>> alice, bob = Person('Alice', 1), Person('Bob', 1)
>>> alice < bob
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: '<' not supported between instances of 'Person' and 'Person'

因为alicebob是自定义类的对象,Python无法对其排序。传统上,您将在类中实现magic方法.lt(),该方法表示小于,以告诉解释器如何比较此类元素。但是,@dataclass装饰器接受一些可选的布尔标志,其中之一是order。当设置为 True时,它会自动生成魔术方法进行比较:

@dataclass(order=True) 
class Person:
    ...

再次运行:

>>> alice < bob
True
>>> bob < alice
False

最后,您可以利用namenumber属性,来观察函数向列表添加Person的位置:

>>> sorted_people = [Person('John', 1)]
>>> bisect.insort_left(sorted_people, Person('John', 2))
>>> bisect.insort_right(sorted_people, Person('John', 3))
>>> sorted_people
[John(2), John(1), John(3)]

在Python中实现二分查找

请记住,除非您有充分的理由,否则不应该实现该算法。重新发明轮子几乎没有实际意义。库代码已非常成熟,在生产环境中经过实际用户的测试,并且具有由多个贡献者提供的广泛功能。

在此,我们只做实验意义上的算法实现。实现我们实现一个find_index函数。

假设所有元素都已排序,则可以在序列的相对两端设置上下边界:

def find_index(elements, value):
 left, right = 0, len(elements) - 1

现在,您要标识中间元素以查看其是否具有所需的值。可以通过取两个边界的平均值来计算中间索引:

def find_index(elements, value):
    left, right = 0, len(elements) - 1
 	middle = (left + right) // 2

接下来,您可以完成序列或将序列分成两部分,然后继续搜索结果的一半:

def find_index(elements, value):
    left, right = 0, len(elements) - 1
    middle = (left + right) // 2

 	if elements[middle] == value: 
 		return middle 
 	if elements[middle] < value: 
 		left = middle + 1 
 	elif elements[middle] > value: 
 		right = middle - 1

如果中间的元素是匹配项,则返回其索引。否则,如果它太小,则需要将下边界向上移动。如果太大,则需要向下移动上限。

为了继续下去,您必须将大多数步骤封闭在一个循环中,当下边界超过上边界时,该步骤将停止:

def find_index(elements, value):
    left, right = 0, len(elements) - 1

	while left <= right:
		middle = (left + right) // 2
        if elements[middle] == value: 
            return middle 
        if elements[middle] < value: 
            left = middle + 1 
        elif elements[middle] > value: 
            right = middle - 1

换句话说,只要下边界低于或等于上边界,您就想进行迭代。否则,将没有匹配项,并且该函数将隐式返回None

按键搜索最终目的是为了查看对象的属性,而不是其文字值。您可以在find_index()中加入key参数:

def find_index(elements, value, key):
    left, right = 0, len(elements) - 1

	while left <= right:
		middle = (left + right) // 2
		middle_element = key(elements[middle])
		
        if elements[middle] == value: 
            return middle 
        if elements[middle] < value: 
            left = middle + 1 
        elif elements[middle] > value: 
            right = middle - 1

但是,您得记住使用key搜索时,必须使用相同的方式对列表进行排序:

>>> fruits = ['orange', 'plum', 'watermelon', 'apple']
>>> fruits.sort(key=len)
>>> fruits
['plum', 'apple', 'orange', 'watermelon']
>>> fruits[find_index(fruits, key=len, value=10)]
'watermelon'
>>> print(find_index(fruits, key=len, value=3))
None

上例中fruits[find_index(fruits, key=len, value=10)],fruits使用key=len排序,在find_index函数中使用key=len进行标识计算,需要找到长度为10(value=10)的字符串'watermelon'。

当然,我们可以使用identity函数自定义find_indexkey

def identity(element):
    return element

def find_index(elements, value, key=identity):
    ...

或者,您可以使用匿名lambda表达式:

def find_index(elements, value, key=lambda x: x):
    ...

我们继续增加2个功能函数,contains 是否包含元素,find返回元素值:

def find_index(elements, value, key):
    ...

def contains(elements, value, key=identity):
    return find_index(elements, value, key) is not None

def find(elements, value, key=identity):
    index = find_index(elements, value, key)
    return None if index is None else elements[index]

现在,我们来进行一个小小的实验。有一群人,其中有些人有共同的名字或姓氏,该怎么办?例如,在人们中间可能有一个Smith家庭或几个小伙子按名字叫John:

from dataclasses import dataclass

@dataclass(order=True)
class Person:
    name: str
    surname: str

people = [
    Person('Bob', 'Williams'),
    Person('John', 'Doe'),
    Person('Paul', 'Brown'),
    Person('Alice', 'Smith'),
    Person('John', 'Smith'),
]

注意,使用该order属性可以自动生成魔术方法,以便按所有字段比较类的实例。

我们按'surname'进行排序和搜索,您可以使用内置operator模块的attrgetter()函数方便地定义键功能:

>>> from operator import attrgetter
>>> by_surname = attrgetter('surname')
>>> people.sort(key=by_surname)
>>> people
[Person(name='Paul', surname='Brown'),
 Person(name='John', surname='Doe'),
 Person(name='Alice', surname='Smith'),
 Person(name='John', surname='Smith'),
 Person(name='Bob', surname='Williams')]

请注意,现在Person是按surname升序排序的。有John Smith和Alice Smith,但是二分查找surname为Smith仅得一个结果:

>>> find(people, key=by_surname, value='Smith')
Person(name='Alice', surname='Smith')

要模仿bisect模块bisect_left()bisect_right()实现的功能,在找到重复元素的最左侧实例之前,您要确定是否存在这样的元素:

def find_leftmost_index(elements, value, key=identity):
    index = find_index(elements, value, key)
    if index is not None:
        ...
    return index

如果找到了某个索引,则可以向左看并继续移动,直到遇到带有其他键的元素或没有其他元素为止:

def find_leftmost_index(elements, value, key=identity):
    index = find_index(elements, value, key)
    if index is not None:
        while index >= 0 and key(elements[index]) == value:
            index -= 1
        index += 1
    return index

越过最左边的元素后,您需要将索引向右移动一个位置。

查找最右边的实例非常相似,但是您需要翻转条件:

def find_rightmost_index(elements, value, key=identity):
    index = find_index(elements, value, key)
    if index is not None:
        while index < len(elements) and key(elements[index]) == value:
            index += 1
        index -= 1
    return index

现在,您将向右移动直到列表的结尾,而不是向左移动。使用这两个功能,您可以查找所有重复项:

def find_all_indices(elements, value, key=identity):
    left = find_leftmost_index(elements, value, key)
    right = find_rightmost_index(elements, value, key)
    if left and right:
        return set(range(left, right + 1))
    return set()

最后,您可以定义更多抽象函数来完善Python二分查找:

def find_leftmost(elements, value, key=identity):
    index = find_leftmost_index(elements, value, key)
    return None if index is None else elements[index]

def find_rightmost(elements, value, key=identity):
    index = find_rightmost_index(elements, value, key)
    return None if index is None else elements[index]

def find_all(elements, value, key=identity):
    return {elements[i] for i in find_all_indices(elements, value, key)}

本文在算法实现上就到此为止,在原文中还有更多的实现细节与代码编写中需要考虑的问题,包括整数溢出,堆栈溢出,重复元素,浮点舍入等等,毕竟一个能用于生产的算法必须要考虑周全且高度抽象。如果您对进一步完善算法有极大兴趣,可查阅原文,或者尝试查阅一下binary.py

"""
The binary search algorithm.
"""

from typing import Optional, Set, Sequence

from search import T, S, Key, identity


def find_index(
    elements: Sequence[T], value: S, key: Key = identity
) -> Optional[int]:
    """Return the index of value in elements or None."""

    left, right = 0, len(elements) - 1

    while left <= right:
        middle = (left + right) // 2

        middle_element = key(elements[middle])

        if middle_element == value:
            return middle

        if middle_element < value:
            left = middle + 1
        elif middle_element > value:
            right = middle - 1

    return None


def find_leftmost_index(
    elements: Sequence[T], value: S, key: Key = identity
) -> Optional[int]:
    """Return the leftmost index of value in elements or None."""

    index = find_index(elements, value, key)

    if index is not None:
        while index >= 0 and key(elements[index]) == value:
            index -= 1
        index += 1

    return index


def find_rightmost_index(
    elements: Sequence[T], value: S, key: Key = identity
) -> Optional[int]:
    """Return the rightmost index of value in elements or None."""

    index = find_index(elements, value, key)

    if index is not None:
        while index < len(elements) and key(elements[index]) == value:
            index += 1
        index -= 1

    return index


def find_all_indices(
    elements: Sequence[T], value: S, key: Key = identity
) -> Set[int]:
    """Return a set of indices of elements with matching key."""

    left = find_leftmost_index(elements, value, key)
    right = find_rightmost_index(elements, value, key)

    if left and right:
        return set(range(left, right + 1))

    return set()


def find(elements: Sequence[T], value: S, key: Key = identity) -> Optional[T]:
    """Return an element with matching key or None."""
    return _get(elements, find_index(elements, value, key))


def find_leftmost(
    elements: Sequence[T], value: S, key: Key = identity
) -> Optional[T]:
    """Return the leftmost element or None."""
    return _get(elements, find_leftmost_index(elements, value, key))


def find_rightmost(
    elements: Sequence[T], value: S, key: Key = identity
) -> Optional[T]:
    """Return the rightmost element or None."""
    return _get(elements, find_rightmost_index(elements, value, key))


def find_all(elements: Sequence[T], value: S, key: Key = identity) -> Set[T]:
    """Return a set of elements with matching key."""
    return {elements[i] for i in find_all_indices(elements, value, key)}


def contains(elements: Sequence[T], value: S, key: Key = identity) -> bool:
    """Return True if value is present in elements."""
    return find_index(elements, value, key) is not None


def _get(elements: Sequence[T], index: Optional[int]) -> Optional[T]:
    """Return element at the given index or None."""
    return None if index is None else elements[index]
Card image cap
开发者雷

尘世间一个小小的开发者,每天增加一些无聊的知识,就不会无聊了

要加油~~~

技术文档 >> 系列应用 >>
热推应用
Let'sLearnSwift
学习Swift的入门教程
PyPie
Python is as good as Pie
标签