Coding Interview Questions | Search in Rotated Sorted Array

January 22nd, 2024

Search in Rotated Sorted Array Problem Introduction:

This summary will talk about my solution to the search in a rotated sorted array problem as seen on leetcode here. A synopsis of the problem summary will be shown below:

There is an integer array 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] might be rotated at 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.

How do you solve the Search in a Rotated Sorted Array Problem?

Solution:

function search(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

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

    if (nums[left] <= nums[mid]) {
      // Left half is sorted
      if (nums[left] <= target && target < nums[mid]) {
        // Target is in the left half
        right = mid - 1;
      } else {
        // Target is in the right half
        left = mid + 1;
      }
    } else {
      // Right half is sorted
      if (nums[mid] < target && target <= nums[right]) {
        // Target is in the right half
        left = mid + 1;
      } else {
        // Target is in the left half
        right = mid - 1;
      }
    }
  }

  return -1; // Target not found
}

Search in Rotated Sorted Array Solution Summary:

Below is a breakdown of the key aspects of the solution above:

1. Binary Search Approach: The algorithm employs a binary search strategy to efficiently find the target element in the rotated sorted array.

2. Initialization: It initializes two pointers, left and right, pointing to the start and end of the array, respectively.

3. Binary Search Iteration: The algorithm enters a while loop where it continuously narrows down the search space by updating the pointers and checking the middle element.

4. Sorting Check: Within the loop, it checks if the left half or the right half is sorted by comparing elements at left, mid, and right indices.

5. Target Comparison: Based on the sorted half, the algorithm compares the target with the elements in that half to determine in which half the target is likely to be.

6. Pointer Update: The pointers (left and right) are then updated accordingly to narrow down the search space.

7. Result Return: If the target is found, the algorithm returns the index where it is located; otherwise, it returns -1.

Complexities

1. Time Complexity: The time complexity of the solution is O(log n) as it employs a binary search strategy, reducing the search space by half in each iteration.

2. Space Complexity: The space complexity is O(1) as the algorithm uses a constant amount of extra space, regardless of the input size.