Leetcode diary: 153. Find Minimum in Rotated Sorted Array [Binary Search]

This is a new series where I document my struggles of leetcode questions hoping seeing however small of an audience I get gives me the motivation to continue.

link

This question was great, I got to practice modified binary search and after completing and seeing how others they approached it generally, I got something better! The code is the same as the one in discussion but my explanation will be more comprehensive.

The question is that given a rotated sorted array, find the minimum number with O(log n) efficiency.
A rotated array is just how many indexes are everything shifted. So for example in for this [1,2,3,4,5,6,7,8]:
[8,1,2,3,4,5,6,7]
[7,8,1,2,3,4,5,6]
[6,7,8,1,2,3,4,5]
these are all the arrays, they are each shifted to the right by 1 index of the previous.

Before I get right into the possible cases, let's first establish that the mid formula is: Math.floor((left+right)/2);
I believe people also do Math.ceil, I just choose the former cause that was the first version I saw while learning about binary search.

I also return nums[left], another convention.

Now we understood this problem, let's look at the possible scenarios:
1.) nums[mid] > nums[right]:
[3,4,5,6,7,8,1,2]
[2,3,4,5,6,7,8,1]
The above two are examples of such.

In this case, it logically makes sense to look for the right. This is because if mid value is great than the right value, it means that the array has rotated past the mid point. Otherwise, we should get mid < right as in the original array. Therefore, the minimum value is somewhere in the right side of the mid index.
This is also obvious from the example, but explained just for the completeness, proof by example usually don't work 100%.

what we should do in this case is:
left = mid+1.

The +1 here is crucial! This is because we need to handle the edge case when the left or right value contains the answer. Inside this if statement though, only right could = min.
so that's say
left = 0, right=1, so mid=0
and we satisfies nums[mid] > nums[right].
so left === right, which we can terminate and return the answer.

2.) nums[mid] <= nums[right]:
[6,7,8,9,1,2,3,4,5] // answer === mid
[6,7,8,1,2,3,4,5] // answer === mid
[7,8,9,1,2,3,4,5,6] // answer === left of mid
[7,8,1,2,3,4,5,6] // answer === left of mid

We look to the left, this is also handles the case when the initial mid is exactly the answer, so we must do:
right=mid; so the answer will never be excluded in the process.
now that's look at
[1,2] since the opposite is already handled by former
left =0, mid = 0, right=1
we satisfies nums[mid] <= nums[right]
and right=mid, so left === mid and we terminate and return the answer.

Now you'd have to play with the examples provided above to see how the two conditions rotate and push towards the [7,1] or [1,2] endgame. Full code below:

var findMin = function(nums) {
    let left, right, mid;
    left  = 0;
    right = nums.length-1;

    while (left < right) {
        mid = Math.floor((left+right)/2);
        if(nums[mid] > nums[right]) {
            left = mid+1
        } else {
            right = mid
        }
    }

    return nums[left];
}

My first solution is below, it is more methodical in the code itself and sort of self-document, but it is a lot more complex and has weird edge cases that have to be explicitly handled. I know the interviewers would like the above better, but the one below could get you many points even if you don't have the code entirely complete:

var findMin = function(nums) {
    let mid, start, end, midI, prevI, nextI
    start = 0;
    end = nums.length-1;


    while (start < end) {
        midI = Math.floor((start+end)/2);
        prevI = midI-1 > -1 ? midI-1: nums.length-1;
        nextI = midI+1 === nums.length ? 0 : midI+1;

        mid = nums[midI]

        if(nums[prevI] > mid && mid < nums[nextI]) { //7,0,1
            return mid;
        }

        if(nums[start] > mid && mid < nums[end]) {
            // go toward the bigger end
            if(nums[start] > nums[end]) {
                end = midI-1; 
            } else {
                start = midI+1;
            }
        }

        if(nums[start] <= mid && mid > nums[end]) {
            // go toward the smaller end
            if(nums[start] > nums[end]) {
                start = midI+1;
            } else {
                end = midI-1; 
            }

        }

        if(nums[start] < mid && mid < nums[end]) {
            // go toward start
            end = midI-1;
        }
    }

    return nums[start]
};

quick note that nums[start] > mid && mid > nums[end] is not possible due to the array being sorted from smallest to biggest.

The main conceptual difference between the two solution is that one just looks to the right.
I guess this is a kind of intuition that has to be developed. So far I am still looking through every possible case in the highest detail :(

Let me know anything on your mind after reading through this, THANKS!