编写 Python 程序在排序数组中搜索元素

在本教程中，我们将解决排序数组中的一个有趣问题。但有一个转折；给定数组可能在某个索引位置被旋转。这意味着排序数组的几个元素可能在给定的索引处被旋转。为了更好地理解，让我们先理解下面的问题陈述。

问题陈述 -

给定一个升序排序且包含不重复值的列表 list1。它可以在一个未知的枢轴索引 k (1 <= k < list1.length) 处旋转，使得生成的数组为 [list1[k], list1[k+1], ..., list1[n-1], list1[0], list1[1], ..., list1[k-1]] (0 索引)。

假设给定数组是 [4, 5, 6, 7, 8, 9, 10, 11]，并可能在枢轴索引 3 处旋转，变成 [8, 9, 10, 11, 4, 5, 6, 7]。

给定一个可能被旋转后的数组 list1 和一个整数 target，返回 target 的索引；如果不存在，则返回 -1。

示例 - 1

输入: list1 = [4, 5, 6, 7, 0, 1, 2], target = 0

输出 4

示例 - 2

输入: list1 = [4, 5 ,6, 7, 0, 1, 2], target = 3输出: -1

现在我们将找到解决此问题的最佳方法。这是一个有点棘手的问题，但如果我们分解解决方案，我们可以轻松编写代码。让我们理解以下解决方案。

解决方案

对于搜索相关的问题，我们首先会想到实现二分查找算法，因为它是一种简单且效率很高的搜索元素算法。然而，给定的列表必须是已排序的，在我们的例子中，数组是已排序但被旋转了。让我们看下面的数组。

list1 = [4, 5, 6, 7, 0, 1, 2]

如果我们仔细观察，我们可以看到正常数组将是 [0, 1, 2, 4, 5, 6, 7]，并且它在索引 3 处被旋转了。

现在可以看到数组被分成两部分，左部分是排序的 [4, 5, 6, 7,]，右部分是 [0, 1, 2]

让我们用图来表示，以便利用二分查找算法来解决这个问题。

我们绘制一个基本图，该图具有连续的基本递增线，不一定是线性的，但始终是递增的。

因此，新图将如下形成。

现在我们可以找到一个模式来帮助我们编写解决方案。众所周知，二分查找有三个指针 - 左、右和中。数组中有两个部分，它们都独立排序。众所周知，二分查找有三个指针 - 左、右和中。

假设在给定数组 [4, 5, 6, 7, 0, 1, 2] 中，目标值为 0，中点为 6，这意味着如果目标值大于 6，它就不会出现在左侧。

现在我们可以在右侧搜索元素。如果目标值小于中点怎么办？

在这种情况下，4、5 都小于 6，0、1、2 也都小于 6，那么我们如何知道应该在哪一侧搜索呢？

所以这里我们检查列表的最左侧值，如果它小于目标值，那么我们就不需要再在左侧搜索它了。

搜索将从 mid + 1 开始放在右侧。但如果目标值大于最左侧的值，我们就在左侧搜索元素。

现在考虑中值为 1；小于 1 的唯一元素是 0。所以搜索将在左侧进行。我们检查最左侧的值并将其与目标值进行比较，如果它大于最右侧的值。让我们用 Python 代码实现它。

注意 - 要检查中值属于左侧部分还是右侧部分，我们可以通过比较最左侧的值与中值来判断。如果中值大于最左侧的值，则它一定属于左侧部分，反之亦然。

Python 代码 -

输出

The element is at the 4 index

这看起来可能有点复杂，但一旦你理解了这个概念，就会清楚。

时间复杂度

时间复杂度为 O(logN)，因为二分查找需要 log n 次比较来找到元素。空间复杂度为 O(1)，因为我们不需要额外的空间。