Problem Statement #

There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).

Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].

Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.

You must decrease the overall operation steps as much as possible.

Approach($O(n)$) #

Before you proceed, I recommend you to attempt 81. Search in Rotated Sorted Array I as I would straight away use the answer from that question

We can use a modified binary search algorithm to solve this problem. And yes this can’t be solved by regular Binary Search as we can’t be sure in which half of the sorted part are we. In simple words, consider this example which is [2,2,2,2,2,1,3,2].Now our left, right, mid, all will give value 2. Hence we can’t decide in which half shall we continue with search.

So the turnaround it is, the same solution as 81. Search in Rotated Sorted Array I which is if our nums[l]==nums[mid] then increment left pointer and try again.

That is why time complexity for this question in worst case is O(n) (consider [2,2,2,2] and target value 3)

Code #

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int l = 0;
        int r = nums.size()-1;

        while(l<=r){
            int mid = l + ((r-l)>>1);
            cout<<mid<<endl;
            if(nums[mid]==target) return true;
            
            if(nums[l]>nums[mid]){
                if(target>nums[mid] and target>=nums[l] or target<nums[mid])r = mid-1;
                else if(target>nums[mid]) l = mid+1;
                else return false;
            }
            else if(nums[l]<nums[mid]){
                if(target<nums[mid] and target>=nums[l]) r = mid-1;
                else if(target>nums[mid] or (target<nums[mid] and target<nums[l])) l = mid+1;

                else return false;
            }
            else // yea this is the only change literally
                l++;
            


        }
        return false;
    }
};

Time Complexity: $O(n)$ #

Space Complexity: $O(1)$ #

Thanks for reading! See you later🙋‍♂️