Search in Rotated Sorted Array

Clarify the problem:

• The problem requires us to search for a target value in a rotated sorted array.
• We need to implement a function that takes in the array and the target value and returns the index of the target if it exists in the array, or -1 if it doesn't.

Analyze the problem:

• Input: Array of integers, target value.
• Output: Index of the target value or -1 if it doesn't exist.
• Constraints:
  • The array is sorted in ascending order.
  • The array may be rotated at an unknown pivot point.
  • The array does not contain any duplicate elements.
  • The length of the array is between 1 and 10^4.

Design an algorithm:

• We can solve this problem using a modified binary search algorithm.
• The idea is to divide the array into two halves and determine which half is sorted.
• We can then perform a binary search on the sorted half to find the target value.
• If the sorted half does not contain the target, we repeat the process on the other half.

Explain your approach:

• We will implement a modified binary search algorithm to search for the target value.
• First, we initialize the start and end pointers to the first and last indices of the array.
• We enter a loop while the start pointer is less than or equal to the end pointer.
• Inside the loop, we calculate the middle index as (start + end) // 2.
• We check if the middle element is equal to the target. If it is, we return the middle index.
• Otherwise, we check if the left half of the array (from start to middle) is sorted.
• If it is, we check if the target value falls within the sorted range.
• If the target is within the sorted range, we update the end pointer to middle - 1; otherwise, we update the start pointer to middle + 1.
• If the left half is not sorted, then the right half must be sorted.
• In this case, we check if the target value falls within the sorted range of the right half.
• If it does, we update the start pointer to middle + 1; otherwise, we update the end pointer to middle - 1.
• We repeat this process until the target value is found or the start pointer becomes greater than the end pointer.
• If the target value is not found after the loop, we return -1.

Write clean and readable code:

python

class Solution:
    def search(self, nums, target):
        start = 0
        end = len(nums) - 1

        while start <= end:
            middle = (start + end) // 2

            if nums[middle] == target:
                return middle

            if nums[start] <= nums[middle]:
                if nums[start] <= target <= nums[middle]:
                    end = middle - 1
                else:
                    start = middle + 1
            else:
                if nums[middle] <= target <= nums[end]:
                    start = middle + 1
                else:
                    end = middle - 1

        return -1

Test your code:

python

solution = Solution()

nums = [4, 5, 6, 7, 0, 1, 2]
target = 0
index = solution.search(nums, target)
print(index)  # Output: 4

nums = [4, 5, 6, 7, 0, 1, 2]
target = 3
index = solution.search(nums, target)
print(index)  # Output: -1

nums = [1]
target = 0
index = solution.search(nums, target)
print(index)  # Output: -1

nums = [1]
target = 1
index = solution.search(nums, target)
print(index)  # Output: 0

Optimize if necessary:

• The binary search algorithm already has a time complexity of O(log n), which is efficient.
• There is no further optimization needed for this problem.

Handle error cases:

• The code assumes that the input for the search function is a valid list of integers and a target value.
• If the input list is empty, the function will return -1.

Discuss complexity analysis:

• Let N be the length of the input array.
• The time complexity of the solution is O(log N) since we divide the array in half at each step of the binary search.
• The space complexity is O(1) as we only use a constant amount of additional space for the variables.
• The solution is efficient and performs well even for large input sizes.