81. Search in Rotated Sorted Array II

31 Search in Rotated Sorted Array ll

描述不包含相同的元素情况

Input: nums = [4,5,6,7,0,1,2], target = 0

Output: 4

对有序数组进行一定的旋转，进行查找

二分查找and双指针

这是二分查找的变体，

双指针的形式，low = 0, high = length-1;

mid 中间分为两个部分

形式

• nums[mid]< nums[r], 这是有序的，可以在这部分进行二分查找

  - 如果nums[mid]<target<= nums[r] , 则可以抛弃左边部分

  - 否则抛弃右部分

• nums[mid]>nums[r], 则nums[l] 到 nums[mid] 是有序，

  - 如果nums[l]<target<=nums[mid], 则在这左部分进行二分查找

  - 否则抛弃左部分

找出其中满足二分查找的部分

class Solution {
    public int search(int[] nums, int target) {
      if(nums==null||nums.length==0) return -1;
      int n = nums.length;
      int l=0,right = n-1;
        
        while(right>=l)
        {
            int mid = (l+right)/2;
          
            if(nums[mid]==target)
                return mid;
            //在这里也可以换成nums[left], 比较
            if(nums[mid] < nums[right])
            {
                if(nums[mid]<target && nums[r]>=target)
                {
                    l = mid+1;
                }
                else
                    right = mid-1;
            }
            else
            {
                if(nums[l]<= target && nums[mid]>target )
                    right = mid-1;
                else 
                    l = mid+1;
            }
        }
        return -1;
    }
}
           

另一种方式写法情况, 主要跟nums[left]与nums[mid]

public class Solution {
    public boolean search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (target == nums[mid]) return true;
            if (nums[mid] == nums[left]) left++;
            else if (nums[mid] > nums[left]) {
                if (nums[left] <= target && nums[mid] > target) right = mid - 1;
                else left = mid + 1;
            } else {
                if (nums[mid] < target && target <= nums[right]) left = mid + 1;
                else right = mid - 1;
            }
        }
        return false;
    }
}
           

复杂度

二分查找时间复杂度为olog(N), 空间复杂度为O(1)

81题目

• 如果包含相同元素，那么就有可能在两边都有都有相同的元素，
• 你并不知道应该跳向哪一半。解决的办法只能是对边缘移动一步，直到边缘和中间不在相等或者相遇，这就导致了会有不能切去一半的可能。
• 所以最坏情况（比如全部都是一个元素，或者只有一个元素不同于其他元素，而他就在最后一个）就会出现每次移动一步，总共是n步，算法的时间复杂度变成O(n)。代码如下：

所以比较 nums[mid] 与nums[right]， 如果两个相等，则放弃一遍的，放弃右边的

if(nums[mid]==nums[right])
    right--;
           

所以就增加了一种情况，

在31题目中

• nums[mid]>nums[right]
• nums[mid] < nums[right]

在81题中

• nums[mid]<nums[right]
• nums[mid]>nums[right]
• nums[mid] =nums[right]

class Solution {
    public boolean search(int[] nums, int target) {
        if(nums==null||nums.length==0) {return false;}
       
        int n = nums.length;
        
        int l=0,r = n-1;
   
        while(r>=l)
        {
            int mid = (l+r)/2;
            if(nums[mid]==target)
                return true;
           
            
            if(nums[mid] < nums[r])
            {
                if(nums[mid]<target && nums[r]>=target)
                {
                    l = mid+1;
                }
                else
                { r = mid-1;}
            }
            else if(nums[mid]>nums[r])
            {
                if(nums[l]<= target && nums[mid]>target )
                {
                    r = mid-1;
                }
                else
                { 
                    l = mid+1;
                }
            }
            else {
              --r;
            }
        }
        return false;
    }
}