Search in Rotated Sorted Array


  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. Write clean and readable code:

  6. 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
  7. Test your code:

  8. solution = Solution() nums = [4, 5, 6, 7, 0, 1, 2] target = 0 index =, target) print(index) # Output: 4 nums = [4, 5, 6, 7, 0, 1, 2] target = 3 index =, target) print(index) # Output: -1 nums = [1] target = 0 index =, target) print(index) # Output: -1 nums = [1] target = 1 index =, target) print(index) # Output: 0
  9. 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.
  10. 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.
  11. 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.
Next Post Previous Post