来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/search-in-rotated-sorted-array
整数数组 nums 按升序排列,数组中的值 互不相同 。
在传递给函数之前,nums 在预先未知的某个下标$ k$$(0 <= k < nums.length)$上进行了 旋转,使数组变为$ [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]$(下标 从 0 开始 计数)。例如, $[0,1,2,4,5,6,7] $在下标 3 处经旋转后可能变为$ [4,5,6,7,0,1,2]$ 。
给你 旋转后 的数组 nums 和一个整数 target ,如果 nums 中存在这个目标值 target ,则返回它的下标,否则返回 -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
示例 3:
输入:nums = [1], target = 0
输出:-1
这个题目,我直接调用库函数....写了10秒钟,显然我猜不符合题意
1 class Solution: 2 def search(self, nums: List[int], target: int) -> int: 3 if target in nums: 4 return nums.index(target) 5 else: 6 return -1
对于有序数组,可以使用二分查找的方法查找元素。
但是这道题中,数组本身不是有序的,进行旋转后只保证了数组的局部是有序的,这还能进行二分查找吗?答案是可以的。
可以发现的是,我们将数组从中间分开成左右两部分的时候,一定有一部分的数组是有序的。拿示例来看,我们从 6 这个位置分开以后数组变成了 [4, 5, 6] 和 [7, 0, 1, 2] 两个部分,其中左边 [4, 5, 6] 这个部分的数组是有序的,其他也是如此。
这启示我们可以在常规二分查找的时候查看当前 mid 为分割位置分割出来的两个部分$ [l, mid]$ 和$ [mid + 1, r] $哪个部分是有序的,并根据有序的那个部分确定我们该如何改变二分查找的上下界,因为我们能够根据有序的那部分判断出 target 在不在这个部分:
如果$ [l, mid - 1] $是有序数组,且 target 的大小满足 $ [\textit{nums}[l],\textit{nums}[mid])$,则我们应该将搜索范围缩小至$ [l, mid - 1]$,否则在$ [mid + 1, r] $中寻找。
如果 [mid, r] 是有序数组,且 target 的大小满足$ (\textit{nums}[mid+1],\textit{nums}[r]]$,则我们应该将搜索范围缩小至$ [mid + 1, r]$,否则在 $[l, mid - 1] $中寻找。
作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/search-in-rotated-sorted-array/solution/sou-suo-xuan-zhuan-pai-xu-shu-zu-by-leetcode-solut/
来源:力扣(LeetCode)
1 class Solution: 2 def search(self, nums: List[int], target: int) -> int: 3 if not nums: 4 return -1 5 l, r = 0, len(nums) - 1 6 while l <= r: 7 mid = (l + r) // 2 8 if nums[mid] == target: 9 return mid 10 if nums[0] <= nums[mid]: 11 if nums[0] <= target < nums[mid]: 12 r = mid - 1 13 else: 14 l = mid + 1 15 else: 16 if nums[mid] < target <= nums[len(nums) - 1]: 17 l = mid + 1 18 else: 19 r = mid - 1 20 return -1 21 22 作者:LeetCode-Solution 23 链接:https://leetcode-cn.com/problems/search-in-rotated-sorted-array/solution/sou-suo-xuan-zhuan-pai-xu-shu-zu-by-leetcode-solut/ 24 来源:力扣(LeetCode)
原文:https://www.cnblogs.com/Harukaze/p/14627180.html