Search in Rotated Sorted Array (I and II)

Search in Rotated Sorted Array

Suppose a sorted array 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).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

class Solution {
    int process(int A[], int const start, int const end, int const target){
        if (start == end){
            if (target == A[start]) return start;
            else return -1;
        }
        int const half = start + (end-start)/2;
        if ( A[start] <= A[half] && (target <= A[half] && target >= A[start])
          || A[start] > A[half] && (target <= A[half] || target >= A[start])) return process(A, start, half, target);
        else return process(A, half+1, end, target);
    }
public:
    int search(int A[], int n, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        return process(A, 0, n-1, target);
    }
};

II

Search in Rotated Sorted Array II

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

Would this affect the run-time complexity? How and why?

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

class Solution {//with dups, one may not be able to determine to process whether the first half
//or the second half of the array, by just looking at three positions: start, half and end
//e.g. 11111111131
//in this case, both parts must be considered, which rise the worst case to O(n)

bool process(int A[], int const start, int const end, int const target){
        if (start == end){
            if (target == A[start]) return true;
            else return false;
        }
        int const half = start + (end-start)/2;
        if (A[start] == A[half] && A[half] == A[end]) return (process(A, start, half, target) || process(A, half+1, end, target));
        if ( A[start] <= A[half] && (target <= A[half] && target >= A[start])
          || A[start] > A[half] && (target <= A[half] || target >= A[start])) return process(A, start, half, target);
        else return process(A, half+1, end, target);
    }
public:
    bool search(int A[], int n, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        return process(A,0,n-1, target);
    }
};