Search In Rotated Sorted Array

To solve this coding challenge, we need to search for a specific target value within a rotated sorted array. The array is sorted in ascending order but has been rotated at an unknown pivot. Due to the need for an O(log n) runtime complexity, we should use a variation of binary search. Here's a detailed explanation along with pseudocode.

# Explanation

1. Understand the Problem :
• You have an array that was initially sorted in ascending order but then rotated at some pivot point.
• The task is to find the target value in this rotated array and return its index, or -1 if the target is not in the array.
• The constraint of O(log n) runtime complexity suggests that a binary search approach should be used.
2. Binary Search in Rotated Array :
• Initial Setup : Start with two pointers for the binary search:
  left
  at the start of the array and
  right
  at the end of the array.
• Iterate Until Convergence : Perform binary search iterations until the search boundaries converge.
• Midpoint Calculation : Calculate the midpoint,
  mid
  , and check if
  nums[mid]
  is equal to the target.
• Determining Search Boundaries :
• If the left part
  nums[left]
  to
  nums[mid]
  is sorted:
• Check if the target lies within this sorted part, if so adjust the
  right
  pointer to
  mid - 1
  .
• If not, adjust the
  left
  pointer to
  mid + 1
  .
• If the right part
  nums[mid]
  to
  nums[right]
  is sorted:
• Check if the target lies within this sorted part, if so adjust the
  left
  pointer to
  mid + 1
  .
• If not, adjust the
  right
  pointer to
  mid - 1
  .
3. Return Result :
• If the target is found return its index.
• If the loop ends without finding the target, return -1.

Detailed Steps in Pseudocode

4. Initial Setup :

                                            
# Initialize pointers for the binary search
left_pointer = 0
right_pointer = length_of_nums - 1

                                        

5. Binary Search Loop :

                                            
# Perform binary search while the search range is valid
while left_pointer <= right_pointer:
# Calculate the midpoint index
mid_index = (left_pointer + right_pointer) // 2

# Check if the midpoint element is the target
if nums[mid_index] == target:
# Target found, return the index
return mid_index

# Determining if the left side is sorted
if nums[left_pointer] <= nums[mid_index]:
# Check if the target is within the sorted left part
if nums[left_pointer] <= target < nums[mid_index]:
# Adjust the right_pointer to narrow the search to the left side
right_pointer = mid_index - 1
else:
# Adjust the left_pointer to narrow the search to the right side
left_pointer = mid_index + 1
else:
# Otherwise, the right part must be sorted
# Check if the target is within the sorted right part
if nums[mid_index] < target <= nums[right_pointer]:
# Adjust the left_pointer to narrow the search to the right side
left_pointer = mid_index + 1
else:
# Adjust the right_pointer to narrow the search to the left side
right_pointer = mid_index - 1

                                        

6. Return -1 if Not Found :

                                            
# Target not found in the array, return -1
return -1

                                        

# Final Summary

By using binary search with the aforementioned steps, we efficiently reduce the search space in each iteration, ensuring the runtime complexity meets the O(log n) requirement. The approach hinges on leveraging the sorted characteristics of the array, even after a rotation, to guide the search process.