algoadvance

You are given an integer array nums sorted in ascending order (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]). You must search for target in nums and if you find it, return its index. Otherwise, return -1.

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. Can the array contain duplicate values?
    • No, the problem specifies that all values in the array are distinct.
  2. Is the array always rotated, or could it be a regular sorted array sometimes?
    • The array may or may not be rotated. It could be a regular sorted array.
  3. Can the array be empty?
    • Yes, if the array is empty, simply return -1.

Strategy

We can leverage a modified binary search to achieve the desired O(log n) runtime. Here’s a step-by-step breakdown of the approach:

  1. Initialize pointers: Start (low) at the beginning of the array and end (high) at the end of the array.
  2. Find mid-point: Calculate the mid-point of the current segment.
  3. Check if mid-point is target: If the mid-point element is the target, return its index.
  4. Determine sorted half:
    • If the left half is sorted (nums[low] <= nums[mid]):
      • Check if the target lies within the left half (nums[low] <= target < nums[mid]). If so, move the high pointer to mid - 1.
      • Otherwise, move the low pointer to mid + 1.
    • If the right half is sorted (nums[mid] <= nums[high]):
      • Check if the target lies within the right half (nums[mid] < target <= nums[high]). If so, move the low pointer to mid + 1.
      • Otherwise, move the high pointer to mid - 1.
  5. Repeat: Continue this until the pointers overlap or the target is found.

Code

def search(nums, target):
    low, high = 0, nums.length - 1

    while low <= high:
        mid = (low + high) // 2
        
        if nums[mid] == target:
            return mid

        # Left half is sorted
        if nums[low] <= nums[mid]:
            if nums[low] <= target < nums[mid]:
                high = mid - 1
            else:
                low = mid + 1
        # Right half is sorted
        else:
            if nums[mid] < target <= nums[high]:
                low = mid + 1
            else:
                high = mid - 1

    return -1

Time Complexity

The time complexity of this algorithm is ( O(\log n) ) because it uses binary search, continuously dividing the search range by half.

Space Complexity

The space complexity is ( O(1) ) because it only uses a constant amount of additional space for the pointers and the mid index.

Try our interview co-pilot at AlgoAdvance.com