ASSIGNMENT 20

Source: Dev.to

Problem Statement

You are given a sorted array that has been rotated at an unknown index.
Your task is to find the index of a target element.

Constraints

• Even though the array is rotated, one half of the current search interval is always sorted.
• At any point, either the left half or the right half is sorted, which allows binary search to be applied.

Algorithm Strategy

1. Compute mid = (low + high) // 2.
2. If nums[mid] equals the target, return mid.
3. Determine which half is sorted:
   • Left half sorted (nums[low] <= nums[mid]):
     • If target lies in [nums[low], nums[mid]), search the left half (high = mid - 1).
     • Otherwise, search the right half (low = mid + 1).
   • Right half sorted (otherwise):
     • If target lies in (nums[mid], nums[high]], search the right half (low = mid + 1).
     • Otherwise, search the left half (high = mid - 1).
4. Repeat while low <= high. If the loop ends without finding the target, return -1.

Implementation (Python)

def search(nums, target):
    low, high = 0, len(nums) - 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

Example

nums = [4, 5, 6, 7, 0, 1, 2]
target = 0
index = search(nums, target)   # returns 4

• Initial mid points to 7 (index 3); the left half [4,5,6,7] is sorted.
• Since target (0) is not in the left half, the algorithm moves to the right half.
• The process continues until it finds 0 at index 4.

Complexity Analysis