33. Search in Rotated Sorted Array

Search in Rotated Sorted Array

Problem Description 

An integer array is nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= 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,5,6,7] it might be rotated at the pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

 

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3:

Input: nums = [1], target = 0
Output: -1

 

Constraints:

• 1 <= nums.length <= 5000
• -104 <= nums[i] <= 104
• All values  nums are unique.
• nums is an ascending array that is possibly rotated.
• -104 <= target <= 104

Approach) Binary Search

In reality, the solution is not that different from a normal binary search; we simply have to accommodate the complexity. This is handled by adding an extra step to the aforementioned logic, which becomes “Is the left-hand side ordered?
If yes, is the target greater than or equal to array[left] and less than array[middle] (AKA on the left side)? If no, is the target greater than or equal to array[middle] (AKA on the right side)?”.

This is because once you pivot or rotate an array at a single point, half of the array will still be ordered in a standard ascending fashion, meaning we can still apply the same logic to that side, and by doing so, identify which side the number belongs to.

Code:

var search = function (nums, target) {
    let low = 0;
    let high = nums.length - 1;

    while (low < high) {
        const middle = Math.floor((low + high) / 2);
        if (nums[middle] == target) return middle;

        // If the left side is ordered
        if (nums[low] <= nums[middle]) {
            // Number is in the left side
            if (target >= nums[low] && target < nums[middle]) {
                high = middle;
            }
            // Number is in the right side
            else {
                low = middle + 1;
            }
        }
        // Right side is ordered
        else {
            // Number is in the right side
            if (target > nums[middle] && target <= nums[high]) {
                low = middle + 1;
            }
            // Number is in the left side
            else {
                high = middle;
            }
        }
    }

    // Reached the final number; return it if it matches the target, else target was not found
    return nums[low] == target ? low : -1;
};

So what exactly are we doing here? Well in simple terms, we’re repeatedly diving the array of numbers in 2 and looking at each side to see if it contains our target number. 
We continue this process until we find our target number, either because we find it at the middle point, or because we get down to our last available number, at which point we’ve either found the target or can safely say that the target was not present in the array.

OR

var search = function(nums, target) {
    let left = 0, right = nums.length-1;
    while(left < right){
      const mid = left + Math.floor((right - left)/2)
      if(nums[mid]===target) return mid
      // When middle element is less than the last element
      if (nums[mid] < nums[right]) {
            if (target > nums[mid] && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        } 
        // When middle element is greater than the last element
        else {
            if (target > nums[mid] || target < nums[left]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
    }
    return left
};

Time Complexity: O(log n)
Space Complexity: O(1)

Approach) Cheat

If, like me, you saw this question and thought “isn’t that incredibly simple?”, you’d be right. A standard brute force approach would simply be to loop through all numbers in the array, looking for the target, like so:

Code:

var search = function (nums, target) {
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === target) return i;
    }
    return -1;
};

Even better, we can use JavaScript’s built-in indexOf() method, which not only finds a value in an array but even returns the correct response (-1) if the value can’t be found.
Code:

var search = function (nums, target) {
    return nums.indexOf(target);
};

But both of these solutions require every value in the array to be checked, which of course makes them inefficient. By splitting our array in the earlier outlined binary search method, we reduce the number of checks required dramatically. 

Additionally, as we are using our own code and not built-in functionality (such as with indexOf()), we can assume that the performance of our approach will remain roughly unchanged between browsers and browser versions.

That said, I would never personally expect a developer to use a binary search over indexOf() in actual production code…

Conclusion

That’s all folks! In this post, we solved LeetCode problem #33. Search in Rotated Sorted Array

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!