[LeetCode] Search in Rotated Array I & II

Search in Rotated Array I

Problem Statement (link):

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.

Analysis:
The naive linear search algorithm gives us O(n) time complexity, where n is the length of the array.

Consider an extend-version of binary search. Let's call entry 0 in the given example the pivot. If we cut the array into half. There are three possibilities:
1) The middle is the pivot. We just return the mid index.
2) The left sub-array is sorted. We the find if the target is in the left sub-array. If so, we repeat this binary search on the left sub-array, otherwise, we do this binary search on the right sub-array.
3) The right sub-array is sorted. We do the same as in 2) but on the right sub-array.

This algorithm ensures O(log n) time complexity.

The catch here is that we cannot easily figure out if the target is in a mis-ordered sub-array by comparing it with the start and end values of the array. But this extend-version binary search ensures that (at least) one of the two sub-arrays is sorted.

Code:

class Solution {
public:
    int search(int A[], int n, int target) {
        int left=0; int right=n-1; int mid;
        while(left<=right) {
            mid = (left+right)/2;
            if (target==A[mid]) return mid;
            if (A[left]<=A[mid]) {   // left is sorted
                if (target>=A[left] && target<A[mid])    // target belongs to the left subarray
                    right = mid-1;
                else
                    left = mid+1;
            }
            else {  // left is not sorted, right is sorted
                if (target>A[mid] && target<=A[right])   // target belongs to the right subarray
                    left = mid+1;
                else
                    right = mid-1;
            }
        }
        return -1;
    }
};

Take-aways:
This algorithm can be thought as a generalized version of binary search.

Search in Rotated Array II

Problem Statement (link):

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.

Analysis:
This problem is basically the same as previous except it allows duplicates in the array.

How would duplicates affect the algorithm? Yes, we cannot easily determine if a sub-array is sorted by comparing its start and end.

However, if we simply skip the start of the sub-array if it's same as the end value, just two extra lines of code could solve this problem.

Code:

class Solution {
public:
    bool search(int A[], int n, int target) {
        int left=0; int right=n-1; int mid;
        while(left<=right) {
            mid=(left+right)/2;
            if (target==A[mid]) return true;
            // If left is sorted
            if (A[left]<A[mid]) {
                if (target>=A[left] && target<A[mid])
                    right=mid-1;
                else
                    left=mid+1;
            }
            // If right is sorted
            else if (A[left]>A[mid]) {
                if (target>A[mid] && target<=A[right])
                    left=mid+1;
                else
                    right=mid-1;
            }
            else    // A[left]==A[mid]
                left++;
        }
        return false;
    }
};