Leetcode diary: 33. Search in Rotated Sorted Array

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

Binary search on steroids!! This is probably a good question to keep coming back to every so often so that you can check whether you have forgotten modified binary search problems.

Given an array of sorted distinct integers, and the fact that each of them is rotated by some random constant K indices, find the index where the target resides or return -1. K is not given.
The question specifies that you have to do this in log N time.

Since it has to be log N, it must means binary search. So the questions is how do you do binary search in a rotated array?

Recall that binary search requires the array to be sorted, but that's not really the case in a sorted array that was then rotated. So we can have: [4,5,6,7,8,9,1,2,3]. How would we go about finding, say 6 in the array?

scroll after you think you have some idea how to do binary search on rotated sorted array first ...
.
.
.
.
.
.
.
.
.
.
.
.
.
The answer is that what if you find the inflection index, aka the index of the smallest value in the array, and then do 2 binary search on this array? We can do one that starts from 0 and ends at inflection -1 and the other inflection to end of array.

So how do we go about modifying the binary search ?
recall that this is the general formula for binary search:

function binarySearch (nums, target) {
    let start,mid,end;
    start = 0; end = nums.length-1;

    while (start <= end) {
        mid = Math.floor((start+end)/2);
        if(nums[mid] === target) return mid;

        if (mid > target) {
            end = mid-1;
        } else {
            start = mid+1 
        }
    }

}

You should definitely have this (or a version of this) memorized. The question then becomes how do we do this to find the inflection point?
The binary search has two main parts:
1.) what is the target
2.) how do we move if mid != target
We don't exactly have a target value for the array, since the inflection point number value can be anything. We only know that it is the smallest. However, we also know that this is a rotated sorted array. This means that all elements are supposed to be smaller to bigger, but because of the rotation, some index somewhere goes from bigger to smaller.
So we can modify the mid check with:
if(nums[mid-1] > nums[mid]).
If the array is actually unrotated, then can we still get the inflection point? The answer is yes. Technically the nice thing about this specific binary search formula is that the in the specific case of unrotated array, the start value will be the smallest value index, which is 0 of course.

Now the question is how do we move without a target? The mental gap is that binary search relies on sorted array, but more technically, a sense of definitive direction. Would we have a definitive sense of direction? Technically yes, this what could happen
1.) nums[mid] > nums[end]
2.) nums[mid] < nums[end]

nums[mid] > nums[end] happens when the rotation has past (nums.length/2), this means that the inflection is at the later half, like: [3,4,5,6,7,8,1,2]
if not past half length rotation:
[5,6,7,8,1,2,3,4]
[7,8,1,2,3,4,5,6]

nums[mid] < nums[end] means the rotation hasn't gone too far, so we can go left side to find the smallest value

So what we should do to find inflection is:

    let start, mid, end;
    start = 0; end = nums.length-1;

    while ( start <= end ) { //find inflection
        mid = Math.floor((start+end)/2);

        if(nums[mid] === target) { return mid } 
        if(nums[mid-1] > nums[mid] ) { start = mid; break; }

        if(nums[mid] > nums[end]) {
            start = mid+1; //find later half
        }
        else {
            end = mid-1; //find in first half
        }
    }

    const inflection = start;

Note that in interview, you'll probably want to run through a simple case like [7,1] and prove that you'll get start as inflection.

Now that we have the inflection done, that's literally 95% of the work! The rest is to run through 2 binary searches one ends with inflection-1 while the other starts at inflection and that's it! Full code below:

var search = function(nums, target) {
    let start, mid, end;
    start = 0; end = nums.length-1;

    while ( start <= end ) { //find inflection
        mid = Math.floor((start+end)/2);

        if(nums[mid] === target) { return mid } 
        if(nums[mid-1] > nums[mid] ) { start = mid; break; }

        if(nums[mid] > nums[end]) {
            start = mid+1;
        }
        else {
            end = mid-1;
        }
    }

    const inflection = start;

    start = 0;
    end = inflection - 1;
    while ( start <= end ) { //<= to not check start after while ends
        mid = Math.floor((start+end)/2);

        if(nums[mid] === target) { return mid }

        if(nums[mid] > target) {
            end = mid-1;
        }
        else {
            start = mid+1;
        }
    }

    start = inflection;
    end = nums.length - 1;
    while ( start <= end ) { //<= to not check start after while ends
        mid = Math.floor((start+end)/2);

        if(nums[mid] === target) { return mid }

        if(nums[mid] > target) {
            end = mid-1;
        }
        else {
            start = mid+1;
        }
    }

    return -1;

};

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