编写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] 我们用图来表示它,利用二分搜索算法来解决这个问题。 我们画一个基本的图,它有连续的基本递增的直线,不一定是线性的,但总是递增的。 ![]() 因此,新的图形将形成如下图所示。 ![]() 现在我们可以找到一个模式来帮助我们写出解决方案。我们知道二分搜索中有三个指针——左,右,中,数组中有两个部分,都是独立排序的。我们知道二分查找中有三个指针——左、右、中。 假设在给定的数组中[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模块
|