在 Python 中查找旋转排序数组中的元素

使用二分查找，我们可以在 O(log(n)) 的时间复杂度内找到给定排序数组或列表中的元素，其中 n 是列表中数字的数量。现在让我们将这个排序数组或列表在任意一个支点上旋转。但是，我们不知道支点，也不能在操作中使用它。例如，如果数组 = [1, 2, 3, 4, 5, 6, 7] 在支点 3 处旋转，那么新数组将是 array_rotated = [4, 5, 6, 7, 1, 2, 3]。

本教程的问题陈述是在旋转排序数组中查找一个特定的数字。同样在 O(log(n)) 的时间复杂度内。

示例输入和输出

输入: array = [4, 6, 8, 10, 12, 14, 0, 2]; target = 6

输出: 存在于索引 1

输入: array = [8, 10, 12, 14, 0, 2, 4, 6]; target = 23

输出: 在数组中未找到

输入: array = [20, 30, 40, 0, 10]; target = 40

输出: 存在于索引 2

假设： 我们将假设数组包含唯一的元素，即数组中没有重复的元素。

朴素方法

在此方法中，我们将首先尝试找到旋转支点。然后将原始数组分成两个子数组。我们将在这些已排序的子数组中执行二分查找。查找支点元素的逻辑是，它是唯一一个当我们从左向右遍历数组时，会比其最后一个元素小的元素。使用此逻辑，我们将找到一个支点。这两个子数组将是单独排序的数组。因此，我们可以在这两个子数组上应用二分查找并找到元素。

算法

输入数组 = [4, 5, 6, 7, 1, 2, 3]

我们需要搜索的元素 = 2

1) 找到数组的支点。将数组分成两个子数组。(支点 = 3) (元素 7 的索引)。

2) 现在，调用二分查找函数并将两个子数组传递给函数。

(a) 如果我们要搜索的元素大于数组的第 0 个元素，则应用此逻辑

(b) 否则，我们将搜索右子数组

(由于 2 小于第 0 个元素，即 4，因此将在右子数组中搜索该元素)

3) 如果我们能在选定的子数组中找到该元素，则返回该元素的索引。否则返回 -1。

我们将用 Python 实现这个算法

代码

输出

The pivot of the array is: 3
The index of 2 in the [4, 5, 6, 7, 1, 2, 3] array is: 5

复杂度分析

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

我们首先使用二分查找来查找支点，然后使用二分查找在子数组中查找元素。

空间复杂度：此程序占用 O(1) 的额外内存空间。我们没有使用任何额外的空间来存储数组。

更好的解决方案

方法：与其应用两次二分查找，不如在一次二分查找中解决问题。我们将修改算法以获得所需的结果。我们将创建一个递归函数，该函数将接受低高索引指针、数组和目标元素。该函数将返回目标元素在旋转排序数组中的索引。

1. 找到中间点 mid = (l + h)/2
2. 如果键存在于中间点，则返回 mid。
3. 否则，如果 arr[l..mid] 已排序
   1. 如果要搜索的键位于 arr[l] 到 arr[mid] 的范围内，则在 arr[l..mid] 上递归。
   2. 否则，在 arr[mid+1..h] 上递归。
4. 否则 (arr[mid+1..h] 必须已排序)
   1. 如果要搜索的键位于 arr[mid+1] 到 arr[h] 的范围内，则在 arr[mid+1..h] 上递归。
   2. 否则，在 arr[l..mid] 上递归。

下面是上述思想的实现

代码

输出

Index: 2

复杂度分析

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

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

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

如何处理重复项？

如果数组包含重复元素，则不可能在 O(log n) 的时间复杂度内搜索索引。例如，如果我们想在数组 [1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1] 中搜索 0 的索引，那么我们不知道该元素可能存在于哪个子数组中。由于我们无法决定子数组，因此我们必须搜索整个数组，因此时间复杂度为 O(n)。