51-Find Minimum in Rotated Sorted Array

This was tricky for me. It took me about an hour and a half to really understand.

This is the form my understanding finally took:

Getting over what part of this is binary search and what isn’t The first confusing thing about this problem was that once we can identify a sorted list where l is less than r, which happens to be the familiar starting point of binary search - that’s exactly when we stop doing binary search.

In this problem, we are just looking for the lowest value. So under those circumstances of l <= r, l is probably going to be the min value. We don’t need to binary search it.

So then what are we binary searching? We are binary searching for that condition. We calculating this middle value to get to a situation where l <= r as quickly as possible.

And the way we are doing that is mostly from an important thing we know, which is that as long as !(l <= r), there are two halves of our range. On the left side of our range somewhere, we will never find the minimum value. We can only find it on the right side of that divide. So our question becomes just, is mid on the right side or the left side?

We can determine this by checking if mid is more than or less than nums[l]. If it’s more than nums[l], we know mid is on the left section, and we should constrict our window to only look to the right of it. Also, by being more than another number, we’ve disqualified the possibility of mid’s value being the min value.

On the other hand, if mid is LESS THAN nums[l], we’re on that right section! We have to consider that the mid could be the minimum value. So we save it as our min value and move on by cutting out the right side of our window and searching the left of it.

Then, moving forward, we overwrite the mid value we wrote if our new l<=r. But that might not happen. We may have to do a few more subdivisions before our mid is more than our left. I think that at this point, it’s completely safe to say as soon as our mid is more than our left, l<=r, since as long as we’re on the right section of the split, mid is less than right.

function findMin(nums: number[]): number {
    let l = 0
    let r = nums.length-1
    let res = nums[0]
 
    while (l <= r){
        if (nums[l] <= nums[r]){
            res = Math.min(res, nums[l])
            break
        }
 
        // so in every other case we don't have a sorted range - l is more than r! Because of the pivot or break point
        const mid = Math.floor((l+r)/2)
        if (nums[mid]>=nums[l]){ 
            l=mid+1
        } else {
            r=mid-1
            res = nums[mid]
        }
    }
 
    return res
};