查找排序数组中元素的第一个和最后一个位置

在本教程中，我们将解决一个 Python 问题，即在排序数组中查找元素的第一个和最后一个位置。问题陈述是我们给出一个按非递减顺序排序的整数数组，并找到给定目标值的起始和结束位置。

示例 -

示例 2

示例 3

让我们理解以下解决方案。

解决方案 - 1：朴素方法

在这种方法中，我们遍历给定数组的元素，检查数组中的元素，并跟踪找到元素的第一个和最后一个出现索引。让我们通过以下示例来理解。

示例 -

输出

[-1, -1]

解释 -

在上面的代码中，我们定义了 find_first_and_last_occurrence() 函数，它接受数组（arr）和目标元素（target）作为输入。我们初始化两个变量 first_occurrence 和 last_occurrence，用于存储目标元素在数组中第一次和最后一次出现的索引。

然后，我们使用 for 循环遍历数组，并检查每个元素是否等于目标。如果我们找到匹配项，并且这是我们第一次遇到目标元素，则更新 first_occurrence 索引。随着我们遍历数组，我们将 last_occurrence 索引不断更新为目标元素的最新出现位置。

最后，我们返回 first_occurrence 和 last_occurrence 索引。

时间复杂度为 O(n)，辅助空间为 O(1)。

解决方案 - 2：使用二分查找

让我们使用二分查找算法来解决这个问题。

示例 -

在上面的代码中，我们首先定义了两个二分查找函数 find_first_occurrence 和 find_last_occurrence，分别用于查找目标元素在排序数组中第一次和最后一次出现的索引。

然后，find_first_and_last_occurrence 函数使用这两个二分查找函数来获取给定数组中目标元素第一次和最后一次出现的索引。

最后的测试代码演示了如何使用示例排序数组和目标元素来使用该函数，如果找到该元素，则打印第一次和最后一次出现的索引，或者如果数组中不存在该元素，则打印一条消息。

解决方案 - 3

要获取第一次出现，第一个二分查找会在数组中查找目标数字的任何一次出现。找到匹配项时，我们记录索引并继续在左子数组中搜索，即当前索引左侧的元素。

在右子数组中，将执行相同的过程来查找数字的最后一次出现。让我们通过以下示例来理解。

示例 -

输出

[3, 4]

解决方案 - 3：使用内置函数

让我们理解下面的例子。

示例 -

输出

[3, 4]

解释 -

在此解决方案中，使用 index() 方法查找列表中目标元素第一次出现的索引。要查找最后一次出现，我们再次使用 index()，但这次是对列表的反转版本 (arr[::-1]) 进行操作，然后计算最后一次出现索引相对于原始列表的索引。