find-minimum-in-rotated-sorted-array

gistfile1.cpp

/*
https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/


//Linear search: O(n)
class Solution {
public:
    int findMin(vector<int> &num) {
        int min = INT_MAX;
        
        for(int i=0; i< num.size() ; ++i) {
            if(min > num[i]) min = num[i];
        }
        
        return min;
    }
};*/

/*
//modified binary search: O(log n)
pick the middle element of the given subarray
comparison 1)left-end 2) right-end
if( right-end < mid || left-end > mid), then the 'start' element should be that side.
*/
 
class Solution {
public:
    int findMin(vector<int> &num) {
        int left = 0;
        int right = num.size()-1;
        int min = 0;
        
        if(num.size() == 1) { //exception 
            return num[0];    
        }
        
        while(left < right) {
            int mid = (left+right)/2;
            if(num[mid] > num[right]) {
                left = mid;
            } else if(num[mid] < num[left]) {
                right = mid;
            } else {
                
                return num[0];   
            }
            
            if(abs(left-right) <= 1) {
                if(num[left] < num[right]) {
                    
                    return num[left];
                } else {
                    
                    return num[right];    
                }
            }
        }
    } 
};