Javatpoint标志
Javatpoint标志

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

在本教程中,我们将解决排序数组中一个有趣的问题。但有一个转折;给定的数组可以在某个下标位置旋转。这意味着排序数组中的少数元素可以在给定的下标处旋转。为了更好地理解它,让我们理解下面的问题陈述。

问题陈述-

数组以list1的形式给出,这些值按升序排列。它可以以未知的主索引k (1 <= k < list1.length)旋转,这样得到的数组是[list1[k], list1[k+1],…, list1[n-1], list1[0], list1[1],…, list1[k-1]] (也就是).

假设给定的数组是[4,5,6,7,8,9,10,11],它可以以主轴索引3旋转,变成[8,9,10,11,4,5,6,7]。

给定一个可能的旋转后的数组list1和一个整数目标,返回目标的索引;如果不存在,返回-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]

我们用图来表示它,利用二分搜索算法来解决这个问题。

我们画一个基本的图,它有连续的基本递增的直线,不一定是线性的,但总是递增的。

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

因此,新的图形将形成如下图所示。

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

现在我们可以找到一个模式来帮助我们写出解决方案。我们知道二分搜索中有三个指针——左,右,中,数组中有两个部分,都是独立排序的。我们知道二分查找中有三个指针——左、右、中。

假设在给定的数组中[4,5,6,7,0,1,2]目标值为0中间是6,这意味着如果目标值大于6,它将不会从左侧退出。

现在我们可以搜索右边的元素。如果目标值小于中间值怎么办?

在这种情况下,4,5小于6 0,1,2小于6,那么我们怎么知道要搜索哪边呢?

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

搜索将被放置在右边的中间+ 1。但如果目标值大于最左边的值,则搜索左边的元素。

现在考虑中值为1;唯一小于1的元素是0。所以搜索会在左边进行。我们检查最左边的值,如果它大于最右边的值,就将它与目标值进行比较。让我们使用Python代码来实现它。

注意:为了检查中间的值是属于左边还是右边,我们可以使用compare从最左边的值到中间,如果中间的值大于最左边的值,那么它一定属于左边,反之亦然。

Python代码-

输出:

元素在第4下标处

这可能看起来有点复杂,但一旦理解了这个概念。会很清楚的。

时间复杂度

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


下一个话题 Python中的Pathlib模块





Youtube 观看视频请加入我们的Youtube频道:现在加入

反馈


帮助他人,请分享

脸谱网 推特 pinterest

学习最新教程


准备


热门的技术


B.Tech / MCA






Baidu
map