# LeetCode : 0153. Find Minimum in Rotated Sorted Array (array)
###### tags:`leetcode`

#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <unordered_map>
using std::vector;
using std::unordered_map;
using namespace std;

class BaseVectorPrint {
    public:
        void BasePrint00(vector<int>& num) {
            for (size_t i = 0; i < num.size(); ++i) {
                cout << "[" <<num.at(i) << "]" << "; ";
            }
            cout << endl;
        }

        void BasePrint01(vector<int>& num) {
            for (size_t i = 0; i < num.size(); ++i) {
                cout << num[i] << "; ";
            }
            cout << endl;
        }

        void BasePrint02(vector<int>& num) {
            for (const auto &item : num) {
                cout << item << "; ";
            }
            cout << endl;
        }
        
        void TwoDimensionalPrint(vector<vector<int>> &num){
            for (int i = 0; i < num.size(); i++)
            {
                for (int j = 0; j < num[i].size(); j++)
                {
                    cout << "[" << num[i][j] << "]";
                }
                cout << endl;
            }
        }
};

class Solution01 {
public:
    int findMin(vector<int>& nums) {
        return searchMin(nums, 0, (int)nums.size() - 1);
    }
    int searchMin(vector<int>& nums, int start, int end) {
        if (start == end) return nums[start];
        if (nums[start] < nums[end]) return nums[start];
        int mid = (start + end) / 2;
        // new mid 
        // left and right min check
        return min(searchMin(nums, start, mid), searchMin(nums, mid + 1, end));
    }
//time complexity O(logN)
//space complexity O(1)
};

class Solution02 {
public:
    int findMin(vector<int>& nums) {
        int left = 0;
        int right = nums.size()-1;

        while(left < right){
            printf("Next Run\n");
            int mid = (left + right) / 2;
            printf("mid = %d\n",mid);
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            }
            else if (nums[mid] > nums[left]) {
                right = mid - 1;
            }
            else if (nums[mid] < nums[right]) {
                right = mid;
            }
            else if (nums[mid] < nums[left]) {
                left = mid;
            }

        }
        return nums[left];

        //how to build selection first 
        //1. set selection
        /*
        while(left < right){  // left == right == mid it leave selection
            int mid = (left + right) / 2;
            // add any state
            if (nums[mid] > nums[right]) {
                
            }
            else if (nums[mid] > nums[left]) {
                
            }
            else if (nums[mid] < nums[right]) {
                
            }
            else if (nums[mid] < nums[left]) {
                
            }
        }
        return nums[left];
        */

        //2. add edge leave selection
        /*
        while(left < right){
            int mid = (left + right) / 2;
            //add move left or mid or right
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            }
            else if (nums[mid] > nums[left]) {
                right = mid - 1;
            }
            else if (nums[mid] < nums[right]) {
                right = mid;
            }
            else if (nums[mid] < nums[left]) {
                left = mid;
            }

        }
        return nums[left];
        */
    }
//time complexity O(logN)
//space complexity O(1)
};

int main(void)
{
    BaseVectorPrint printVector;
    Solution02 runfunc;

    vector<int> test01 = {3,4,5,1,2};
    // sampel run;
    // first 
    vector<int> test02 = {4,5,6,7,0,1,2};
    vector<int> test03 = {11,13,15,17};
    vector<int> ans ;
    int intans;

    intans = runfunc.findMin(test02);
    //printVector.BasePrint00(ans);

    printf("%d\n",intans);
    printf("test\n");
    system("pause");
}

> tip check selection
> tip set selection move state (left mid right)