[Leetcode] 153. Find Minimum in Rotated Sorted Array

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

intiial

so bs is the logic but why?

Index: 0 1 2 3 4 5 6
Nums: 4 5 6 7 0 1 2

lets say we are at mid idx =3 so value is 7. we see right vaue is 2, which is smaller than the mid value. So we know we should look towards the right side, not the left cuz after value 7, there will be a point where the value drops and we can find a min value somewhere in the right

sol

class Solution {
    public int findMin(int[] nums) {
        int n = nums.length;
        int left=0, right=n-1;
        while(left<right){
            int mid = left+(right-left)/2;
            if(nums[mid]>nums[right]) left=mid+1;
            else right=mid;
        }
        return nums[left];
    }
}

complexity

log n time
1 space