DSA/C++/LeetCode/0154.cpp at main · spycedcoffee/DSA · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//Solution 1:-
//T : O(n)
class Solution {
public:
    int findMin(vector<int>& nums) {

        int minVal = INT_MAX;

        for(auto c : nums){
            minVal = min(c, minVal);
        }

        return minVal;
    }
};


//Solution 2:- (faster)
//T : O(log n)
class Solution {
public:
    int findMin(vector<int>& nums) {

        int left = 0;
        int right = nums.size() - 1;

        while(left < right){

            int mid = left + (right - left)/2;

            if(nums[mid] > nums[right])
                left = mid + 1;

            else if(nums[mid] < nums[right])
                right = mid;

            else
                right--;
        }

        return nums[left];
    }
};