Blogs Hub

by Sumit Chourasia | Nov 10, 2020 | Category :coding | Tags : algorithm array data-structure leetcode medium

Search in Rotated Sorted Array II - Array - Medium - LeetCode

Search in Rotated Sorted Array II - Array - Medium - LeetCode

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).

You are given a target value to search. If found in the array return true, otherwise return false.

Example 1:

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true
Example 2:

Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false
Follow up:

This is a follow up problem to Search in Rotated Sorted Array, where nums may contain duplicates.
Would this affect the run-time complexity? How and why?

 

public class Solution {
    public bool Search(int[] nums, int target) {
        
        var left = 0;
        var right =  nums.Length-1;
        var mid = -1;
        
        while(left<=right)
        {
            mid = left + (right-left)/2;
            if(nums[mid] == target){ 
                return true;
            }

            // the only difference from the first one, trickly case, just updat left and right
            if( (nums[left] == nums[mid]) && (nums[right] == nums[mid]) ) 
            {
                ++left; 
                --right;
            }
            else if(nums[left] <= nums[mid])
            {
                if( (nums[left]<=target) && (nums[mid] > target) ){ 
                    right = mid-1;
                }
                else {
                    left = mid + 1;
                } 
            }
            else
            {
                if((nums[mid] < target) &&  (nums[right] >= target) ){ 
                    left = mid+1;
                }
                else {
                    right = mid-1;
                }
            }
        }
        return false;
    }
}

Time Complexity: O(logn)

Space Complexity: O(1)