Python 中使用二分查找的第一次出现

在本教程中，我们将学习如何在给定的排序列表中使用二分查找来查找元素第一次出现的索引。我们将在 Python 中实现该算法。但首先，我们需要了解什么是二分查找。

朴素方法

在开始二分查找之前，让我们先看看解决该问题最简单的方法。

我们将运行一个 for 循环，找到 x 时，我们将中断循环并返回变量的当前索引。我们可以使用 Python 的 enumerate 函数同时获取变量的索引。

代码

输出

The first occurrence of 3 in the array is at: 
7

此方法的 time complexity 为 O(n)，其中 n 是数组中的元素数量。这种方法效率不高。当给定的数组未排序时，我们可以考虑使用此方法。

解决此问题的另一种方法是使用 Python 列表的 .index(e) 函数。此函数将返回包含给定元素 e 第一次出现索引的数组索引。

代码

输出

The first occurrence of 3 in the array is at: 
7

二分搜索

例如，我们有一个包含 n 个整数的排序数组或排序的 Python 列表。我们要在此列表中搜索特定的数字。使用 for 循环遍历列表中的每个元素并检查当前元素是否等于我们要查找的数字，其 time complexity 为 O(n)，其中 n 是列表中整数的数量。二分查找是解决此任务的有效方法。

二分查找算法如下：

• 我们将给定的排序列表分成两半。
• 检查目标数字是否等于列表中间位置的元素。如果是，则返回中间元素的索引。
• 如果不是，则检查目标数字大于还是小于列表中间的元素。
• 如果目标数字大于中间元素，我们将丢弃列表的左半部分。如果目标数字小于列表的中间元素，我们将丢弃列表的右半部分。
• 执行上一步后，我们将得到一个新列表，其长度将是原始列表的一半。
• 我们将在新列表上重复步骤 1、2、3 和 4。
• 我们将继续此过程，直到找到元素，或者列表中没有更多元素可供检查。
• 此算法将返回列表中目标数字的索引。如果列表中不存在该元素，即循环在中间中断而未完成，则返回 -1。

二分查找算法的 time complexity 为 O(log(n))。

二分查找第一次出现

现在假设我们要查找的目标数字在列表中出现不止一次。因此，在这种情况下，我们要查找目标数字在列表中的第一次出现。

解决此问题的算法如下：

• 假设我们有一个排序的整数列表，并且我们知道列表中存在重复的数字。设列表为 ints。
• 现在我们必须找到数字 x 在列表中的第一次出现。
• 我们将使用两个指针，分别指向列表的起始索引和结束索引。每次我们丢弃列表的某个半部分时，都需要更新这些指针。新列表将在这些指针的索引之间。我们将这些指针初始化为 s（起始）等于 0，e（结束）等于最后一个索引，即 Python 中列表长度 -1。
• 我们需要在长度为“length”的给定数组中搜索数字 x。我们将定义一个函数来搜索给定数组中 x 的第一次出现。该函数将以数组、数组长度以及需要搜索的数字作为参数。
• 在函数内部，我们初始化了一个变量 result。该变量将在指针在数组中找到 x 时存储索引。变量的默认值设置为 -1，因为如果指针在数组中找不到任何 x，它将返回 -1。这是我们需要遵循的规则。
• 现在我们将启动一个 while 循环。while 循环将一直运行，直到起始索引 s 小于或等于 e。当低索引超过高索引时，循环将停止。
• 在 while 循环内部，我们初始化了一个变量 mid，其值为 (s + e) // 2。此变量将找到由索引 s 和 e 界定的列表的中间索引。
• 现在我们将检查一些条件，以帮助我们决定必须丢弃数组的哪一部分。如果数组中间索引 `mid` 的值为我们要搜索的数字，那么我们将结果存储在 result 中。现在，如果元素出现在数组的中间索引处，并且我们要查找给定数字的第一次出现，那么我们必须在数组的左半部分进行搜索。接下来，如果中间值大于我们要搜索的数字，那么我们必须在数组的左半部分进行搜索。如果中间值小于我们要搜索的数字，那么我们必须在数组的右半部分进行搜索。这样，循环将继续，直到 s 和 e 都指向单个值。循环结束后，result 变量将包含该变量第一次出现时的索引。
• 如果数组中没有 x，result 变量的值将保持不变，因此将返回 -1。

现在我们将学习如何在 Python 中实现此算法。

代码

输出

The first occurrence of 3 is at: 3

现在我们将尝试搜索一个不在列表中的数字。

代码

输出

The first occurrence of 3 is at: -1

此算法的 time complexity 为 O(log(n))。因此，我们已经优化了解决方案。我们已经看到了三种查找元素第一次出现索引的方法。