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;
    }
}