Python中的二分搜索

本教程将学习如何使用 Python 中的二分查找算法在给定列表中查找元素的索引位置。

引言

二分查找是一种在列表中查找特定元素的算法。假设我们有一个包含一千个元素的列表，并且我们需要获取特定元素的索引位置。使用二分查找算法，我们可以非常快速地找到元素的索引位置。

有很多查找算法，但二分查找是最受欢迎的。

要应用二分查找算法，列表中的元素必须已排序。如果元素未排序，请先对其进行排序。

让我们来理解二分查找的概念。

二分查找的概念

在二分查找算法中，我们可以使用以下方法找到元素的位置。

• 递归方法
• 迭代方法

递归方法遵循分治法的技术。在此方法中，一个函数会一遍又一遍地调用自身，直到在列表中找到一个元素。

在迭代方法中，一组语句会重复多次以查找元素在列表中的索引位置。while 循环用于完成此任务。

二分查找比线性查找更有效，因为我们不需要检查列表中的每个索引。列表必须已排序才能实现二分查找算法。

让我们逐步实现二分查找。

我们有一个已排序的元素列表，并且正在查找 45 的索引位置。

[12, 24, 32, 39, 45, 50, 54]

因此，我们在列表中设置了两个指针。一个指针用于表示较小的值，称为 low，第二个指针用于表示较大的值，称为 high。

接下来，我们计算数组中中间元素的值。

现在，我们将要搜索的元素与中间索引值进行比较。在这种情况下，32 不等于 45。因此，我们需要进行进一步比较才能找到元素。

如果我们要搜索的数字等于中间值。则返回 mid，否则继续进行进一步比较。

要搜索的数字大于中间数字，我们将 n 与 mid 右侧的元素进行比较，并将 low 设置为 low = mid + 1。

否则，将 n 与 mid 左侧的中间元素进行比较，并将 high 设置为 high = mid - 1。

重复此过程，直到找到要搜索的数字。

在 Python 中实现二分查找

首先，我们使用迭代方法实现二分查找。我们将重复一组语句并迭代列表中的每个项。我们将找到中间值，直到搜索完成。

让我们通过迭代方法理解上面的程序。

Python 实现

输出

Element is present at index 4

说明

在上面的程序中 -

• 我们创建了一个名为 binary_search() 的函数，它接受两个参数 - 一个要排序的列表和一个要搜索的数字。
• 我们声明了两个变量来存储列表中的最低值和最高值。low 的初始值设置为 0，high 设置为 len(list1) - 1，mid 设置为 0。
• 接下来，我们声明了 while 循环，条件是 lowest 等于且小于 highest。如果尚未找到数字，则 while 循环将继续迭代。
• 在 while 循环中，我们找到中间值并将索引值与我们要搜索的数字进行比较。
• 如果中间索引的值小于 n，我们将中间值加 1 并将其分配给。搜索移至左侧。
• 否则，将中间值减 1 并将其分配给 high。搜索移至右侧。
• 如果 n 等于中间值，则返回 mid。
• 这将一直发生，直到 low 等于且小于 high。
• 如果到达函数末尾，则表示元素不在列表中。我们向调用函数返回 -1。

让我们来理解二分查找的递归方法。

递归二分查找

二分查找可以使用递归方法。在这种方法中，我们将定义一个递归函数，该函数会一直调用自身，直到满足条件。

让我们通过递归函数来理解上面的程序。

Python 程序

输出

Element is present at index 2

说明

上面的程序与之前的程序类似。我们声明了一个递归函数及其基本条件。条件是最低值小于或等于最高值。

• 我们计算中间数字，与上一个程序相同。
• 我们使用 if 语句继续二分查找。
• 如果中间值等于我们要查找的数字，则返回中间值。
• 如果中间值小于我们要查找的值，则我们的递归函数 binary_search() 会再次调用，并将中间值加一并赋给 low。
• 如果中间值大于我们要查找的值，则我们的递归函数 binary_search() 会再次调用，并将中间值减一并赋给 low。

在最后一部分，我们编写了主程序。它与之前的程序相同，但唯一的区别是我们向 binary_search() 函数传递了两个参数。

这是因为我们无法在递归函数中为 low、high 和 mid 分配初始值。每次调用递归函数时，这些变量的值都会重置。这将导致错误的结果。

复杂度

二分查找算法在最佳情况下的复杂度为 O(1)。这发生在我们要查找的元素在第一次比较中就找到时。O(logn) 是二分查找的平均情况和最坏情况复杂度。这取决于找到我们要查找的元素所需的搜索次数。

结论

二分查找算法是查找列表中元素的最高效、最快速的方法。它会跳过不必要的比较。顾名思义，搜索被分为两部分。它专注于列表中靠近我们要搜索的数字的那一部分。

我们已经讨论了两种查找给定数字索引位置的方法。