在 Python 中查找较低的插入点

本教程的问题陈述是：给定一个长度为 n 的已排序数组和一个整数 x，我们需要找到 x 在给定数组中的较低插入索引。任何元素的较低插入索引是插入整数 x 并且数组仍然排序的索引。这意味着第一个元素的索引大于或等于 x。如果 x 大于数组中的所有整数，则将其插入到第 n 个索引，如果它小于所有元素，则将其插入到第 0 个位置。

示例输入和输出

朴素方法

解决此问题的最简单方法是遍历数组并找到较低的插入点。

算法

• 首先，我们将检查给定的整数 x 是否小于数组的第一个元素，然后返回 0；如果它大于矩阵的最大元素，则返回 n。
• 我们将启动一个 for 循环，该循环将从 0 运行到数组长度 - 1。
• 在 for 循环内部，我们将使用 if 语句。借助 if 语句，我们将检查当前元素是否等于或大于 x。
• 如果 if 语句的结果为 True，则函数将返回当前索引。否则，它将继续直到最后一个元素。

以下是算法的实现

代码

输出

The element can be inserted at the index:  1

时间复杂度：此程序的 T时间复杂度为 O(n)。由于我们遍历了每个数组元素，因此在最坏情况下需要 O(n) 时间。

空间复杂度：O(1)。我们没有使用任何额外的内存空间。

改进方法

在此方法中，我们将使用二分查找算法来查找插入点。

算法

• 在此方法中，同样，首先，我们将检查给定的整数 x 是否小于数组的第一个元素，然后返回 0；如果它大于矩阵的最大元素，则返回 n。
• 我们将初始化变量 low = 0、high = n - 1 和 res = 0，并存储大于或等于 x 的元素的索引。然后我们将启动一个 while 循环。
• 我们将检查中间元素是否等于 x，然后我们将 res 中的 mid 存储起来。现在我们需要搜索数组中 x 的第一次出现。在这种情况下，我们需要搜索左子数组。
• 如果中间元素小于 x，我们将搜索右子数组。
• 如果中间元素大于 x，我们将 res 中的中间索引存储起来，并在左子数组中搜索第一个更大的元素。

我们将使用 Python 实现此算法

代码

输出

The element can be inserted at the index:  1 

时间复杂度：此程序的 T时间复杂度为 O(log n)。

我们使用了一个单一的二分查找算法；因此，T时间复杂度为 O(log n)。

空间复杂度：O(1)。我们没有使用任何额外的内存空间。