在Python中搜索旋转排序数组

  • Z时代
  • 2024-01-10
  • 分类：综合

考虑一下我们有一个按升序排序的数组，它以事先未知的某个轴旋转。例如，[0,1,2,4,5,6,7]可能变为[4,5,6,7,0,1,2]。我们为搜索指定了目标值。如果我们可以在数组中获取它，则返回其索引，否则返回-1。我们可以假设数组中不存在重复项。因此，如果数组类似于[4,5,6,7,0,1,2]，则输出将为4.，因为此元素的索引位于索引4处。

为了解决这个问题，我们将遵循以下步骤-

  • 低：= 0，高：=数组长度

  • 从低到高

    • 如果目标<= arr [高-1]并且目标> arr [中]，则低：=中+ 1，否则高：=中

    • 如果目标> = arr [低]而目标<arr [mid]，则高：=中，否则低：=中+ 1

    • 中点找到：=低+（高-低）/ 2

    • 如果arr [mid] =目标，则返回mid

    • 如果arr [low] <= arr [mid]

    • 除此以外

    • 返回-1

    示例(Python)

    让我们看下面的实现以更好地理解-

    class Solution(object):
       def search(self, nums, target):
          low = 0
          high = len(nums)
          while low<high:
             mid = low + (high-low)//2
             if nums[mid] == target:
                return mid
             if nums[low]<=nums[mid]:
                if target >=nums[low] and target <nums[mid]:
                   high = mid
                else:
                   low = mid+1
             else:
                if target<=nums[high-1] and target>nums[mid]:
                   low = mid+1
                else:
                   high = mid
          return -1
    ob1 = Solution()print(ob1.search([4,5,6,7,8,0,1,2], 0))

    输入值

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

    输出结果

    5

    以上是 在Python中搜索旋转排序数组 的全部内容， 来源链接： utcz.com/z/322266.html

    回到顶部