【力扣】搜索旋转排序数组

来源：力扣（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