题目描述（中等难度）

33题的升级版，数组的操作没有变，所谓的旋转数组，就是把有序数组前边若干个数字移动到末尾。区别在于这道题出现了重复的数字，同样是找 target。

解法一

把数组遍历一遍，然后依次判断数字是否相等的解法，当然就不用说了。这里直接在33 题解法三的基础上去修改。33 题算法基于一个事实，数组从任意位置劈开后，至少有一半是有序的，什么意思呢？

比如 [ 4 5 6 7 1 2 3] ，从 7 劈开，左边是 [ 4 5 6 7] 右边是 [ 7 1 2 3]，左边是有序的。

基于这个事实。

如果不加修改，直接放到 leetcode 上跑，发现 nums = [ 1, 3, 1, 1, 1 ] ，target = 3，返回了 false，当然是不对的了。原因就出现在了，我们在判断哪段有序的时候，当 nums [ start ] <= nums [ mid ] 是认为左半段有序。而由于这道题出现了重复数字，此时的 nums [ start ] = 1, nums [ mid ] = 1，但此时左半段 [ 1, 3, 1 ] 并不是有序的，所以造成我们的算法错误。

所以 nums[start] == nums[mid] 需要我们单独考虑了。操作也很简单，参考-on-average-o(n)-worst-case)，当相等的时候，我们只需要让 start++ 就够了。

  2.     int start = 0;
  3.     int end = nums.length - 1;
  4.     while (start <= end) {
  5.         int mid = (start + end) / 2;
  6.         if (target == nums[mid]) {
  7.             return true;
  8.         //左半段有序
  10.             if (target >= nums[start] && target < nums[mid]) {
  11.                 end = mid - 1;
  12.             } else {
  13.                 start = mid + 1;
  14.             }
  15.         } else if(nums[start] == nums[mid]){
  16.             start++;
  18.             if (target > nums[mid] && target <= nums[end]) {
  19.                 start = mid + 1;
  20.             } else {
  21.                 end = mid - 1;
  22.             }
  23.         }
  24.     }
  25.     return false;

时间复杂度：最好的情况，如果没有遇到 nums [ start ] == nums [ mid ]，还是 O（log（n））。当然最差的情况，如果是类似于这种 [ 1, 1, 1, 1, 2, 1 ] ，target = 2，就是 O ( n ) 了。

空间复杂度：O ( 1 )。

总

添加好友一起进步~

如果觉得有帮助的话，可以点击 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情