Leetcode 81 - Search in Rotated Sorted Array II

Link to problem

Problem

There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).

Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].

Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.

You must decrease the overall operation steps as much as possible.

Solution

The “rotation” really did not change anything, it only splits the sorted array into two sorted array. Moreover, we know that all elements in one array will be less or equal to all elements in another array.

Therefore, we could solve the problem by finding the rotation pivot first by iterating the array. Then we could do a binary search on one of the subarray to check if the element exists.

Time complexity of this algorithm will be $O(n)$.

Implementation

Since I’m probably using JavaScript for an interview in the near future, the implementation below is in JS. I have long despise this language, with many of its questionable design. However, since this is what most frontend job uses, I have little choice but to pick up this tool.

// binary search
const binSearch = (nums, target, front, back) => {
    while (front <= back) {
        let mid = Math.floor((front + back)  / 2);
        if (nums.at(mid) > target) back = mid - 1;
        else if (nums.at(mid) < target) front = mid + 1;
        else return true;
    }

    return false;
};

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {boolean}
 */
var search = function(nums, target) {
    let pivot = 0;
    let prev = nums[0];
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] >= prev) prev = nums[i];
        else {
            pivot = i;
            break;
        }
    }

    let front = 0, back = nums.length - 1;
    if (target >= nums[front] && target <= nums[pivot-1])
        return binSearch(nums, target, front, pivot-1);
    else if (target >= nums[pivot] && target <= nums[back])
        return binSearch(nums, target, pivot, back);

    return false;
};