algoadvance

Leetcode 33. Search in Rotated Sorted Array

Problem Statement

You are given an integer array nums sorted in ascending order (not necessarily with distinct values), and an integer target. Suppose 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]).

Given the array nums after the 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

Clarifying Questions:

  1. Q: Could the array be rotated at any index?
    • A: Yes, the array can be rotated at any index.
  2. Q: Are there any duplicates in the array?
    • A: No, the array does not contain duplicate values as per the problem definition for this variant.

Strategy:

The problem requires an O(log n) runtime complexity, which suggests a binary search approach. We can modify the standard binary search to handle the rotation:

  1. Identify the mid-point:
    • If the mid element is equal to the target, return the mid index.
  2. Determine which part of the array is sorted:
    • If the left part (nums[left] to nums[mid]) is sorted:
      • Check if the target is within this range.
    • Otherwise, the right part (nums[mid] to nums[right]) must be sorted:
      • Check if the target is within this range.
  3. Adjust the search range based on the sorted part and target position:
    • If the target lies within the range of the sorted part, adjust the left or right pointers accordingly.

Code:

public class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (nums[mid] == target) {
                return mid;
            }
            
            // Determine if the left half is sorted
            if (nums[left] <= nums[mid]) {
                // Target is in the left sorted part
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            // Otherwise, the right half must be sorted
            else {
                // Target is in the right sorted part
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }

        return -1; // Target not found
    }
}

Time Complexity:

The time complexity of the algorithm is O(log n), as each step effectively halves the search range, characteristic of binary search.

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