- 标签:数组、二分查找
- 难度:中等
描述:给定一个整数数组
要求:从
说明:
- 旋转操作:升序排列的数组 nums 在预先未知的第 k 个位置进行了右移操作,变成了
$[nums[k]], nums[k+1], ... , nums[n-1], ... , nums[0], nums[1], ... , nums[k-1]$ 。
示例:
- 示例 1:
输入:nums = [4,5,6,7,0,1,2], target = 0
输出:4
- 示例 2:
输入:nums = [4,5,6,7,0,1,2], target = 3
输出:-1
原本为升序排列的数组
*
*
*
*
*
*
*
*
*
*
*
*
最直接的办法就是遍历一遍,找到目标值
我们将旋转后的数组看成左右两个升序部分:左半部分和右半部分。
有人会说第一种情况不是只有一个部分吗?其实我们可以把第一种情况中的整个数组看做是左半部分,然后右半部分为空数组。
然后创建两个指针
-
如果
$mid[mid] == target$ ,说明找到了$target$ ,直接返回下标。 -
如果
$nums[mid] \ge nums[left]$ ,则$mid$ 在左半部分(因为右半部分值都比$nums[left]$ 小)。- 如果
$nums[mid] \ge target$ ,并且$target \ge nums[left]$ ,则$target$ 在左半部分,并且在$mid$ 左侧,此时应将$right$ 左移到$mid - 1$ 位置。 - 否则如果
$nums[mid] \le target$ ,则$target$ 在左半部分,并且在$mid$ 右侧,此时应将$left$ 右移到$mid + 1$ 位置。 - 否则如果
$nums[left] > target$ ,则$target$ 在右半部分,应将$left$ 移动到$mid + 1$ 位置。
- 如果
-
如果
$nums[mid] < nums[left]$ ,则$mid$ 在右半部分(因为右半部分值都比$nums[left]$ 小)。- 如果
$nums[mid] < target$ ,并且$target \le nums[right]$ ,则$target$ 在右半部分,并且在$mid$ 右侧,此时应将$left$ 右移到$mid + 1$ 位置。 - 否则如果
$nums[mid] \ge target$ ,则$target$ 在右半部分,并且在$mid$ 左侧,此时应将$right$ 左移到$mid - 1$ 位置。 - 否则如果
$nums[right] < target$ ,则$target$ 在左半部分,应将$right$ 左移到$mid - 1$ 位置。
- 如果
class Solution:
def search(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
if nums[mid] >= nums[left]:
if nums[mid] > target and target >= nums[left]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target and target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
-
时间复杂度:$O(\log n)$。二分查找算法的时间复杂度为
$O(\log n)$ 。 - 空间复杂度:$O(1)$。只用到了常数空间存放若干变量。