题目：

已知存在一个按非降序排列的整数数组 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,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。

你必须尽可能减少整个操作步骤。

 

示例 1：

输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true
示例 2：

输入：nums = [2,5,6,0,0,1,2], target = 3
输出：false
 

提示：

  • 1 <= nums.length <= 5000
  • -104 <= nums[i] <= 104
  • 题目数据保证 nums 在预先未知的某个下标上进行了旋转
  • -104 <= target <= 104

进阶：

  • 这是 搜索旋转排序数组 的延伸题目，本题中的 nums  可能包含重复元素。
  • 这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/search-in-rotated-sorted-array-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

 注意：这里面有重复元素，对于像[1,3,1,1,1]这种数组，很难通过nums[left]和nums[mid]比较来判断两个升序区间的位置，但是可以通过比较nums[mid]与nums[left]是否相同，来排除重复数字，如果nums[mid] == nums[left]说明有重复的数字，让left向右移动来排除重复数字。

题目中说将数据进行旋转，这样的话就会将搜索区间从中间一分为二，位于中间的元素nums[mid]一定会在其中一个有序的区间中。当nums[mid]与target相等时，直接返回true。后续不等的情况，讨论mid与左边界的大小关系，分为两种情况：

1.mid的值大于等于左边界时：nums[mid] >= nums[left]

  •  此时在区间[left, mid – 1]内的元素一定是有序的，如果target在[left, mid -1]里，即nums[left] <= target < nums[mid]，此时设置right = mid – 1;
  • 上一个区间的反面，target在区间[mid, right]中，left == mid；

2.mid的值小于左边界时：nums[mid] < nums[left]

  •  此时在区间[mid, right]内的元素一定是有序的，为了两种情况left和right变化一致，这里是假设如果target在[mid, right]里，即nums[mid] <= target <=nums[right]，此时设置left = mid ;
  • 上一个区间的反面，target在区间[left, mid – 1]中，right == mid – 1；

注意：这里的区间存在[mid, right]，为了防止区间只有两个元素的时候，向下取整会让mid一直和left相同，出现死循环，故需要变成向上取整mid = left + (right – left + 1) / 2。

java代码（left < right）：

 1 class Solution {
 2     public boolean search(int[] nums, int target) {
 3         int left = 0, right = nums.length - 1;
 4         while (left < right){
 5             int mid = left + (right - left + 1) / 2;
 6             if (nums[mid] == target) return true;
 7             if (nums[left] == nums[mid]){
 8                 left++;
 9                 continue;
10             }
11             if (nums[mid] >= nums[left]){
12                 if (target < nums[mid] && target >= nums[left]){
13                     right = mid - 1;
14                 }else{
15                     left = mid;
16                 }
17             }else{
18                 if (target >= nums[mid] && target <= nums[right]){
19                     left = mid;
20                 }else{
21                     right = mid - 1;
22                 }   
23             }
24         }
25         return nums[left] == target;
26     }
27 }

python代码：

 1 class Solution:
 2     def search(self, nums: List[int], target: int) -> bool:
 3         left, right = 0, len(nums) - 1
 4         while left < right:
 5             mid = left + (right - left + 1) // 2
 6             if nums[mid] == target:
 7                 return True
 8             if nums[left] == nums[mid]:
 9                 left += 1
10                 continue
11             if nums[mid] >= nums[left]:
12                 if nums[left] <= target < nums[mid]:
13                     right = mid - 1
14                 else:
15                     left = mid
16             else:
17                 if nums[mid] <= target <= nums[right]:
18                     left = mid
19                 else:
20                     right = mid - 1
21         return True if nums[left] == target else False

java代码（left <= right）：

 1 class Solution {
 2     public boolean search(int[] nums, int target) {
 3         int left = 0, right = nums.length - 1;
 4         while (left <= right){
 5             int mid = left + (right - left) / 2;
 6             if (nums[mid] == target) return true;
 7             if (nums[left] == nums[mid]){
 8                 left++;
 9                 continue;
10             }
11             //左边有序
12             if (nums[mid] >= nums[left]){
13                 if (target < nums[mid] && target >= nums[left]){
14                     right = mid - 1;
15                 }else{
16                     left = mid + 1;
17                 }
18             }else{
19                 if (target > nums[mid] && target <= nums[right]){
20                     left = mid + 1;
21                 }else{
22                     right = mid - 1;
23                 }   
24             }
25         }
26         return false;
27     }
28 }

原文地址：http://www.cnblogs.com/liu-myu/p/16920921.html

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！ 2. 分享目的仅供大家学习和交流，请务用于商业用途! 3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！ 4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！ 5. 如有链接无法下载、失效或广告，请联系管理员处理！ 6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！ 7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！ 8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载 声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性