algoadvance

Leetcode 33. Search in Rotated Sorted Array

Problem Statement

You are given an integer array nums sorted in ascending order (with distinct values), and an integer target. Suppose that nums is rotated at some pivot unknown to you beforehand (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You should search for target in nums and if you find it, return its index. Otherwise, return -1.

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

Clarifying Questions

  1. Can nums be empty?
    • Yes, and if it is empty, the function should return -1.
  2. Are there any constraints on the array nums?
    • Yes, nums will contain distinct integers and will be rotated at some pivot.
  3. What should be returned if the target is not found?
    • Return -1.

Strategy

We can utilize a modified binary search to achieve the O(log n) runtime complexity. The key insight is to determine which part of the array is normally ordered, and then decide whether the target lies within that range or in the other part.

  1. Set low to 0 and high to nums.size() - 1.
  2. While low <= high:
    1. Calculate mid as the middle index of low and high.
    2. Check if nums[mid] equals the target. If it does, return mid.
    3. Determine which side of the array is normally ordered:
      • If nums[low] <= nums[mid], the left side is normally ordered:
        • Check if the target is between nums[low] and nums[mid]. If it is, narrow the search to the left by setting high to mid - 1.
        • Otherwise, search the right side by setting low to mid + 1.
      • Otherwise, the right side is normally ordered:
        • Check if the target is between nums[mid] and nums[high]. If it is, narrow the search to the right by setting low to mid + 1.
        • Otherwise, search the left side by setting high to mid - 1.
  3. If the loop ends without finding the target, return -1.

Code

#include <vector>
using namespace std;

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if (nums.empty()) return -1;

        int low = 0;
        int high = nums.size() - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            
            if (nums[mid] == target) {
                return mid;
            }

            if (nums[low] <= nums[mid]) {
                // Left side is normally ordered
                if (nums[low] <= target && target < nums[mid]) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            } else {
                // Right side is normally ordered
                if (nums[mid] < target && target <= nums[high]) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
        }

        return -1;
    }
};

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI