LeetCode 33. 搜索旋转排序数组 | Python

LeetCode 33. 搜索旋转排序数组 | Python

33. 搜索旋转排序数组

题目来源：https://leetcode-cn.com/problems/search-in-rotated-sorted-array/

题目

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

示例 1:

输入: nums = [4,5,6,7,0,1,2], target = 0

输出: 4

示例 2:

输入: nums = [4,5,6,7,0,1,2], target = 3

输出: -1

解题思路

思路：二分查找

题目中，要求算法时间复杂度必须是 O(log n) 级别，在这里，其实提示可以使用二分查找的方法。

有个地方需要注意的是，二分查找，要求的是列表的元素必须是有序的。在这里，虽然原始数组是按照升序排序的，但数组在某个未知的点进行旋转之后，列表只有局部才是有序的。

但其实这里并不会冲突，因为将经过旋转的列表分割成两部分时，一定有一个部分是有序的。

直接以上面的示例 1 为例，[4, 5, 6, 7, 0, 1, 2]，如果将数组分割成 [4, 5, 6] 和 [7, 0, 1, 2]，那么前面 [4, 5, 6] 这部分是有序的。这在其他符合这些条件的数组一样是成立的。

上面提到数组分为两部分，那么可以考虑从在中点的位置进行划分，将原数组划分为 [left, mid] 和 [mid + 1, right] 两部分。

当将旋转后的数组分成上述两部分时，现在要考虑的就是 target 值，会落在哪个区间？当 target 值落在有序那部分的区间中，这个比较好理解，这个时候上下边界是确定的，题目中也说明【可以假设数组中不存在重复的元素。】，那么有且只有一个元素与之匹配。

现在具体分析判断 target 会落在哪个区间：

如果 [left, mid - 1] 这部分是有序的，且 target 落在 [nums[left], nums[mid]) 这个区间，那么就可以将搜索的范围缩小到 [left, mid - 1]，否则的话，将在 [mid + 1, right] 这个区间中进行搜索；

如果 [mid, right] 这部分是有序的，且 target 落在 (nums[mid+1], nums[right]]，那么就在 [mid + 1, right] 这个区间进行搜索，否则在 [left, mid - 1] 这个区间进行搜索。

下面是具体的代码实现。

代码实现

class Solution:

def search(self, nums: List[int], target: int) -> int:

# nums 为空时，直接返回 -1

if not nums:

return -1

# 初始左右边界

left, right = 0, len(nums) - 1

# 判断哪部分区间是有序的

# 判断 target 会落在哪个区间

while left <= right:

# 数组划分为两部分

mid = (left + right) // 2

# 如果目标值与划分区间的元素相等时，直接返回

if nums[mid] == target:

return mid

# 判断区间是否有序

# 这里表示 [left, mid - 1] 是有序的

if nums[0] <= nums[mid]:

# target 落在 [left, mid - 1] 这个区间

if nums[0] <= target < nums[mid]:

# 重新划分右边界

right = mid - 1

# target 落在 [mid + 1, right] 这个区间

else:

# 重新划分左边界

left = mid + 1

# nums[0] > nums[mid] 时，表示 [mid + 1, right] 有序

else:

# target 落在 [mid + 1, right] 时

if nums[mid] < target <= nums[right]:

# 重新划分左边界

left = mid + 1

else:

# target 落在 [left, mid - 1] 这个区间

# 重新划分左边界

right = mid - 1

return -1

实现结果

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。