在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处。
为了解决这个问题，我们将遵循以下步骤-
低：=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