Binary Search in Rotated Sorted Array

Binary Search in Rotated Sorted Array

The Binary Search Algorithm for a rotated sorted array finds a target value in an array that was originally sorted in ascending order but rotated at some pivot point. The algorithm modifies standard binary search to handle the rotation by determining which half of the array is sorted and checking if the target lies in that sorted half. It assumes no duplicates in the array and has a time complexity of O(log n), where n is the length of the array.

Example:

• Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0
• Output: 4
• Explanation: The target value 0 is found at index 4 in the rotated sorted array.

Program (Python - Binary Search in Rotated Sorted Array)

The following Python code implements the Binary Search algorithm for a rotated sorted array with O(log n) time complexity, assuming no duplicates.

def search(nums, target):
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if nums[mid] == target:
            return mid
        
        # Check if left half is sorted
        if nums[left] <= nums[mid]:
            # Check if target is in left half
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # Right half is sorted
        else:
            # Check if target is in right half
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    
    return -1

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

Output

For the input nums = [4, 5, 6, 7, 0, 1, 2] and target = 0, the output is:

4

Explanation: The target value 0 is found at index 4 in the rotated sorted array.

Practice It Yourself

Enter a rotated sorted array of numbers (comma-separated, no duplicates) and a target value to find its index using the Binary Search algorithm.