Find Minimum in Rotated Sorted Array Solutions in C++

// Source : https://oj.leetcode.com/problems/find-minimum-in-rotated-sorted-array/
// Author : Hao Chen
// Date   : 2014-10-20



#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>
#include <vector>
using namespace std;

/* 
 *  Obveriously, to search any sorted array, the binary search is the common sense.
 * 
 *  To solve this problem, the idea is same as the search in rotated sorted array.
 */
int findMin(vector<int> &num) {

    int low=0, high=num.size()-1;

    while(high-low>1){
        int mid = low + (high-low)/2;
        // Chek the array if it is non-rotated, then just return the first element.
        if (num[low] < num[mid] && num[mid] < num[high]){
            return num[low];
        }

        // The array is rotated
        // Split it into two part, the minimal value must be the rotated part
        
        // if the left part is rotated, warch the left part
        if (num[low] > num [mid]){
            high = mid;
            continue;
        }
        // if the right part is rotated, search the right part.
        if (num[mid] > num[high]){
            low = mid;
            continue;
        }
    }
    // the array only has 1 element
    if (high == low) return num[low];

    // the array has 2 elements
    return num[low] < num[high] ? num[low] : num[high];

}


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)); 

    int expectedMin, actualMin;
    int *a = new int[cnt];
    for(int n=0; n<=cnt; n++) {
        printf("--------------------------------------\n");
        for(int i=0; i<cnt; i++){
            a[i]=i;
        }
        expectedMin = a[0];
        //printArray(a, cnt);
        int rotate_pos = random() % cnt;
        //rotate_pos=2;
        printf("rotate=%d\n", rotate_pos);
        rotate_array(a, cnt, rotate_pos);
        printArray(a, cnt);

        vector<int> num(a, a+cnt);
        actualMin = findMin(num);
        cout << "findMin = " << actualMin << "   " << (expectedMin==actualMin ? "passed" : "failed") << endl;

    }
    delete[] a;

    return 0;
}

#include <vector>
using std::vector; using std::next; using std::prev; using std::advance;

class Solution {
public:
    int findMin(vector<int> &num) {
        auto beg = num.begin();
        for (auto end = std::prev(num.end()); beg < end; )
        {
            if (*beg < *end) break;
            auto mid = (end - beg) >> 1;
            *beg <= *next(beg, mid) ? advance(beg, mid+1) : advance(end, -mid);
        }
        return *beg;
    }
};

/// Source : https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description/
/// Author : liuyubobobo
/// Time   : 2018-09-07

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;


/// Linear Scan
/// Time Complexity: O(n)
/// Space Complexity: O(1)
class Solution {
public:
    int findMin(vector<int>& nums) {
        return *min_element(nums.begin(), nums.end());
    }
};


int main() {

    vector<int> nums1 = {3, 4, 5, 1, 2};
    cout << Solution().findMin(nums1) << endl; // 1

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

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

    vector<int> nums4 = {7, 1, 2, 3, 4, 5, 6};
    cout << Solution().findMin(nums4) << endl; // 1

    return 0;
}

/// Source : https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description/
/// Author : liuyubobobo
/// Time   : 2018-09-07

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;


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

        assert(nums.size() > 0);
        if(nums.size() == 1)
            return nums[0];
        if(nums.size() == 2)
            return min(nums[0], nums[1]);

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

            if(nums[l] > nums[mid])
                l = l + 1, r = mid;
            else if(nums[r] < nums[mid])
                l = mid + 1;
            else
                assert(false);
        }
        return nums[l];
    }
};


int main() {

    vector<int> nums1 = {3, 4, 5, 1, 2};
    cout << Solution().findMin(nums1) << endl; // 1

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

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

    vector<int> nums4 = {7, 1, 2, 3, 4, 5, 6};
    cout << Solution().findMin(nums4) << endl; // 1

    return 0;
}