Search in Rotated Sorted Array II Solutions in C++

// Source : https://oj.leetcode.com/problems/search-in-rotated-sorted-array-ii/
// Author : Hao Chen
// Date   : 2014-06-29



// Using the same idea "Search in Rotated Sorted Array"
// but need be very careful about the following cases:
//   [3,3,3,4,5,6,3,3] 
//   [3,3,3,3,1,3]
// After split, you don't know which part is rotated and which part is not.
// So, you have to skip the ducplication
//   [3,3,3,4,5,6,3,3] 
//          ^       ^
//   [3,3,3,3,1,3]
//            ^ ^
class Solution {
public:
    bool search(int A[], int n, int key) {
        if (n<=0) return false;
    
        if (n==1){
            return (A[0]==key) ? true : false;
        }
        int low=0, high=n-1;
        while( low<=high ){
    
            if (A[low] < A[high] && ( key < A[low] || key > A[high]) ) {
                 return false;
            }
            
            //if dupilicates, remove the duplication
            while (low < high && A[low]==A[high]){
                low++;
            }
    
            int mid = low + (high-low)/2;
            if ( A[mid] == key ) return true;
    
            //the target in non-rotated array
            if (A[low] < A[mid] && key >= A[low] && key< A[mid]){
                high = mid - 1;
                continue;
            }
            //the target in non-rotated array
            if (A[mid] < A[high] && key > A[mid] && key <= A[high] ){
                low = mid + 1;
                continue;
            }
            //the target in rotated array
            if (A[low] > A[mid] ){
                high = mid - 1;
                continue;
            }
            //the target in rotated array
            if (A[mid] > A[high] ){
                low = mid + 1;
                continue;
            }
            
            //reach here means nothing found.
            low++;
        }
        return false;
    }
    
    
};

class Solution {
public:
    bool search(int A[], int n, int target) {
        if (n<0) return false;
        for (int l=0, r=n-1; l<=r; )
        {
            int m = (l+r) >> 1;
            if (target == A[m] || target == A[l] || target == A[r]) return true;
            else if ((A[l] < A[m] && target > A[l] && target < A[m]) || (A[l] > A[m] && target > A[l])) r = m-1;
            else if ((A[m] < A[r] && target > A[m] && target < A[r]) || (A[m] > A[r] && target < A[r])) l = m+1;
            else ++l, --r;
        }
        return false;
    }
};

/// Source : https://leetcode.com/problems/search-in-rotated-sorted-array-ii/
/// Author : liuyubobobo
/// Time   : 2020-10-14

#include <iostream>
#include <vector>

using namespace std;


/// Finding break point and binary search
/// Time Complexity: O(n)
/// Space Complexity: O(1)
class Solution {
public:
    bool search(vector<int>& nums, int target) {

        if(nums.size() == 0) return false;

        int p = 0;
        for(p = 0; p + 1 < nums.size(); p ++)
            if(nums[p] > nums[p + 1]) break;

        int l = 0, r = p;
        while(l <= r){
            int mid = l + (r - l) / 2;
            if(nums[mid] == target) return true;
            if(target < nums[mid]) r = mid - 1;
            else l = mid + 1;
        }

        l = p + 1, r = nums.size() - 1;
        while(l <= r){
            int mid = l + (r - l) / 2;
            if(nums[mid] == target) return true;
            if(target < nums[mid]) r = mid - 1;
            else l = mid + 1;
        }

        return false;
    }
};


int main() {

    vector<int> nums1 = {4,5,6,7,0,1,2};
    cout << Solution().search(nums1, 0) << endl;

    vector<int> nums2 = {4,5,6,7,8,1,2,3};
    cout << Solution().search(nums2, 8) << endl;

    return 0;
}