Search in Rotated Sorted Array Solutions in C++

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



#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int binary_search(int A[], int n, int key); 
int binary_search(int A[], int l, int h, int key); 
int rotate_search(int A[], int l, int h, int key);

int search1(int A[], int n, int target);
int search2(int A[], int n, int target); 

int search(int A[], int n, int target) {
    if (random()%2){
        return search1(A, n, target);
    }
    return search2(A, n, target);
}
/*
 *    Using binary search idea, 
 *    1) Spliting the array to two part, one part should be non-rotated, another one is rotated.
 *    2) Checking the "key" whether is possible in non-rotated sorted part.
 *        2.1) if it is, then go to the classcial binary searh.
 *        2.2) if it not, then keep spliting the rorated part.
 *
 */
int search1(int A[], int n, int key) {
    if (n<=0) return -1;

    if (n==1){
        return (A[0]==key) ? 0 : -1;
    }
    int low=0, high=n-1;
    while( low<=high ){

        if (A[low] <= A[high] && ( key < A[low] || key > A[high]) ) {
             return -1;
        }

        int mid = low + (high-low)/2;
        if ( A[mid] == key ) return mid;
    
        //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;
        }
    }
    return -1;
}

int search2(int A[], int n, int target) {
    if (n<=0) return -1;

    if (n==1){
        return A[0]==target?0:-1;
    }        

    if ( A[0] < A[n-1] ){
        return binary_search(A, n, target);
    }else{
        return rotate_search(A, 0, n-1, target);
    }
}

int rotate_search(int A[], int low, int high, int key ) {
    
    if (low > high){
        return -1;
    }
    if (low==high){
        return A[low]==key?low:-1;
    }        
    
    int mid = low + (high-low)/2;
    if ( A[mid] == key ) return mid;

    if (A[low] < A[mid] && key >= A[low] && key< A[mid]){
        return binary_search(A, low, mid-1, key);
    }
    if (A[mid] < A[high] && key > A[mid] && key <= A[high] ){
        return binary_search(A, mid+1, high, key);
    }
    if (A[low] > A[mid] ){
        return rotate_search(A, low, mid-1, key);
    }
    if (A[mid] > A[high] ){
        return rotate_search(A, mid+1, high, key);
    }
    return -1;
}

int binary_search(int A[], int n, int key) {
    int low = 0;
    int high = n-1;
    while (low <= high){
        int mid = low +(high-low)/2;
        if (A[mid] == key){
            return mid;
        }
        if ( key> A[mid] ) {
            low = mid+1;
        }else{
            high = mid-1;
        }
    }
    return -1;
}

int binary_search(int A[], int low, int high, int key) {
    //(low+high)/2 could encounter overflow issue
    int mid = low+(high-low)/2;
    if (low > high){
        return -1;
    }
    if (A[mid]==key){
        return mid;
    }
    if (key > A[mid]){
        binary_search(A, mid+1, high, key);
    }else{
        binary_search(A, low, mid-1, key);
    }

}

void rotate_array(int a[], int n, int pos){
    int i, from=0;
    pos = pos % n;
    if (n<=0) return;

    int tmp = a[0];
    
    for(int i=0, step=0; step<n && i<pos; step++){
        int to;
        if (from-pos < 0) {
            to = n-pos+from; 
        }else{
            to = from-pos;
        }
        int t ;
        t = a[to];
        a[to] = tmp; 
        tmp = t;
        from = to;
        if ( to == i ){
            i++;
            from++;
            tmp = a[from];
        }
    }
    
}

void printArray(int A[], int n) {
    printf("{");
    for(int i=0; i<n; i++) {
        printf("%d, ", A[i]);
    }
    printf("}\n");
}

int main(int argc, char** argv)
{

    int cnt=20;

    if (argc>1) {
        cnt = atoi(argv[1]);
    }

    srand(time(NULL)); 

   for(int n=0; n<=cnt; n++) {
        printf("--------------------------------------\n");
        int *a = new int[cnt];
        for(int i=0; i<cnt; i++){
            a[i]=i*2;
        }
        //printArray(a, cnt);
        int rotate = random() % cnt;
        //rotate=2;
        //printf("rotate=%d\n", rotate);
        rotate_array(a, cnt, rotate);
        printArray(a, cnt);
        int target = random() % (2*cnt);
        //target=6;
        printf("target=%d\n", target);
    
        int idx = search(a, cnt, target);
        if ( idx<0 ){
            printf("not found!\n");
        }else{
            printf("a[%d] = %d\n", idx, a[idx]); 
        }
        
        delete[] a;
   }

    return 0;
}

class Solution {
public:
    int search(int A[], int n, int target) {
        for (int i = 0, j = n-1; i <= j; )
        {
            int m = (i + j) >> 1;
            if (target == A[m]) return m;
            else if ((A[i] <= target && target < A[m]) || (A[m] < A[i] && (target < A[m] || A[i] <= target))) j = m - 1;
            else if ((A[m] < target && target <= A[j]) || (A[j] < A[m] && (target <= A[j] || A[m] < target))) i = m + 1;
            else break;
        }
        return -1;
    }
};

/// Source : https://leetcode.com/problems/search-in-rotated-sorted-array/description/
/// Author : liuyubobobo
/// Time   : 2018-06-22

#include <iostream>
#include <vector>

using namespace std;

/// Binary Search
/// Time Complexity: O(logn)
/// Space Complexity: O(1)
class Solution {
public:
    int search(vector<int>& nums, int target) {

        int l = 0, r = nums.size() - 1;
        while(l <= r){
            //cout << "l : " << l << " r : " << r << endl;
            int mid = l + (r - l) / 2;
            if(nums[mid] == target)
                return mid;
            //cout << "mid : " << mid << endl;

            if(target < nums[mid]){
                if(nums[l] <= nums[r] || nums[mid] < nums[l])
                    r = mid - 1;
                else if(target >= nums[l])
                    r = mid - 1;
                else
                    l = mid + 1;
            }
            else{ // target > nums[mid]
                if(nums[l] <= nums[r] || nums[mid] > nums[r])
                    l = mid + 1;
                else if(target >= nums[l])
                    r = mid - 1;
                else
                    l = mid + 1;
            }
        }

        return -1;
    }
};


int main() {

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

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

    vector<int> nums3 = {1, 3};
    int target3 = 3;
    cout << Solution().search(nums3, target3) << endl;
    // 1

    vector<int> nums4 = {5, 1, 3};
    int target4 = 5;
    cout << Solution().search(nums4, target4) << endl;
    // 0

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

    return 0;
}

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

#include <iostream>
#include <vector>

using namespace std;

/// Find max value and do Binary Search
/// Time Complexity: O(n)
/// Space Complexity: O(1)
class Solution {
public:
    int search(vector<int>& nums, int target) {

        if(nums.size() == 0) return -1;
        int max_index = max_element(nums.begin(), nums.end()) - nums.begin();

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

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

        return -1;
    }
};


int main() {

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

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

    vector<int> nums3 = {1, 3};
    int target3 = 3;
    cout << Solution().search(nums3, target3) << endl;
    // 1

    vector<int> nums4 = {5, 1, 3};
    int target4 = 5;
    cout << Solution().search(nums4, target4) << endl;
    // 0

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

    return 0;
}