Python旋转排序数组中的搜索

假设我们有一个按升序排序的数组，并且它在某个未知的枢轴点旋转了。例如，[0,1,2,4,5,6,7]可能会变成[4,5,6,7,0,1,2]。我们给定一个目标值进行搜索。如果我们在数组中找到它，则返回它的索引，否则返回-1。我们可以假设数组中不存在重复元素。因此，如果数组类似于[4,5,6,7,0,1,2]，则输出将为4，因为该元素的索引位于索引4处。

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

• low := 0 high := 数组长度
• 当 low < high
  • 找到 mid: mid := low + (high - low)/2
  • 如果 arr[mid] = target，则返回 mid
  • 如果 arr[low] <= arr[mid]
    • 如果 target >= arr[low] 且 target < arr[mid]，则 high := mid，否则 low := mid + 1
  • 否则
    • 如果 target <= arr[high - 1] 且 target > arr[mid]，则 low := mid + 1，否则 high := 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

Arnab Chakraborty

更新于：2020年4月27日

888 次浏览

启动您的职业生涯

完成课程获得认证

开始