Rotated_Sorted_Array

//rotated sorted array questions:

//Q-1: https://leetcode.com/problems/search-in-rotated-sorted-array/

class Solution {
public:
    int search(vector<int>& a, int key)
    {
       int n=a.size();
       int l=0,r=n-1;
       while(l<=r)
       {
           int mid=l+(r-l)/2;
           if(a[mid]==key) return mid;
           if(a[mid]>=a[l])//left sorted
           {
               if(key<=a[mid]&&key>=a[l])
               {
                   r=mid-1; continue;
               }
               else
               {
                   l=mid+1; continue;
               }
           }
           else//right part sorted
           {
               if(key<=a[r]&&key>=a[mid])
               {
                   l=mid+1; continue;
               }
               else
               {
                   r=mid-1; continue;
               }
           }
       }
        return -1;
    }
};





//Q-2: https://leetcode.com/problems/search-in-rotated-sorted-array-ii/description/


class Solution {
public:
    bool search(vector<int>& a, int key)
    {
        int n=a.size();
        int l=0,r=n-1;
        while(l<=r)
        {
            int mid=l+(r-l)/2;
            if(key==a[mid]) return true;
            if(a[l]<a[mid])//left striclty sorted
            {
                if(key<a[mid]&&key>=a[l])
                {
                    r=mid-1; continue;
                }
                else
                {
                    l=mid+1; continue;
                }
            }
            else if(a[l]==a[mid])
            {
                l++; continue;
            }
            else//right sorted
            {
                if(key<=a[r]&&key>a[mid])
                {
                    l=mid+1; continue;
                }
                else
                {
                    r=mid-1; continue;
                }
            }
        }
        return false;
    }
};