leetcode 81. Search in Rotated Sorted Array II 旋转数组查找+二分查找

水深无声 2022-06-08 02:14 180阅读 0赞

Follow up for “Search in Rotated Sorted Array”:  
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?  
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Write a function to determine if a given target is in the array.

The array may contain duplicates.

这道题很简单，直接遍历即可。也可以使用二分查找。

代码如下：

public class Solution 
    {
        /*
         * 最简单的就是遍历
         * */
        public boolean search(int[] nums, int target)
        {
           if(nums==null || nums.length<=0)
                return false;
           for(int i=0;i<nums.length;i++)
               if(nums[i]==target)
                   return true;
           return false;
        }
    
        /*
         * 二分查找
         * */
        public boolean search2(int[] nums, int target)
        {
            if(nums==null || nums.length<=0)
                return false;
    
            int left=0,right=nums.length-1;
            while(left<=right)
            {
                int mid = (left-right)/2+right;
                if(nums[mid]==target)
                    return true;
    
                if(nums[left]<nums[mid])
                {
                    if(nums[left]<=target&& target<nums[mid])
                        right=mid-1;
                    else
                        left=mid+1;
                }else if(nums[left]>nums[mid])
                {
                    if(nums[mid]<target&&target<=nums[right])
                        left=mid+1;
                    else
                        right=mid-1;
                }else
                    left++;   
            }
    
            return false;
        }
    
    }

下面是C++的做法，我是直接遍历

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    #include <iomanip>
    #include <cstdlib>
    #include <ctime>
    
    using namespace std;
    
    
    
    
    class Solution 
    {
    public:
        bool search(vector<int>& a, int target) 
        {
            if (a.size() <= 0)
                return false;
            int left = 0, right = a.size() - 1;
            while (left <= right)
            {
                int mid = (right - left) / 2 + left;
                if (a[mid] == target)
                    return true;
                else  if (a[left] < a[mid])
                {
                    if (a[left] <= target && target < a[mid])
                        right = mid - 1;
                    else
                        left = mid + 1;
                }
                else if (a[left] > a[mid])
                {
                    if (a[mid] < target && target <= a[right])
                        left = mid + 1;
                    else
                        right = mid - 1;
                }
                else
                    left++;
            }
            return false;
        }
    };