Search in Rotated Sorted Array - Python Solution

1. Introduction

The "Search in Rotated Sorted Array" problem is a variation of binary search. It involves a unique challenge where a sorted array has been rotated at some unknown pivot. The task is to efficiently find a target value in this rotated array. This problem is a good test of understanding how to modify binary search to handle non-standard scenarios.

Problem

An integer array nums, sorted in ascending order and containing distinct values, is rotated at an unknown pivot index k. After rotation, the array becomes [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]. Given nums after the rotation and an integer target, the goal is to return the index of target in nums, or -1 if it is not present. The algorithm should have a runtime complexity of O(log n).

2. Solution Steps

1. Implement a modified binary search to account for the rotated array.

2. Identify the sorted portion of the array in each iteration.

3. Determine if the target lies within the sorted portion or the unsorted portion.

4. Adjust the search range based on where the target is likely to be.

5. Continue the search until the target is found or the search space is exhausted.

3. Code Program

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

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

        # Check if the middle element is the target
        if nums[mid] == target:
            return mid

        # Check if the left half is sorted
        if nums[start] <= nums[mid]:
            # If target is in the left half
            if nums[start] <= target <= nums[mid]:
                end = mid - 1
            else:
                start = mid + 1
        # Right half is sorted
        else:
            # If target is in the right half
            if nums[mid] <= target <= nums[end]:
                start = mid + 1
            else:
                end = mid - 1

    return -1

# Testing the function with examples
print(search([4,5,6,7,0,1,2], 0))
print(search([4,5,6,7,0,1,2], 3))

Output:

4
-1

Explanation:

1. Modified Binary Search: The algorithm uses a binary search but with modifications to handle the rotation.

2. Identifying Sorted Half: In each iteration, it determines whether the left or right half of the array is sorted.

3. Target Search: The search range is adjusted based on whether the target is likely in the sorted or unsorted half.

4. Search Adjustment: Depending on the target's position relative to the middle element, the search space is narrowed down.

5. Result: The function returns the index of the target if found, or -1 if the target is not in the array.