Binary Search in Rotated Sorted Array

Given a sorted array that has been rotated at an unknown pivot (e.g., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]), search for a target value efficiently. A standard binary search won't work directly, but with a few extra checks we can still achieve O(log n) time.

Problem Statement

Given an array nums that was originally sorted in ascending order and then rotated at some pivot, and a target value, return the index of the target if it exists, otherwise return -1.

Approach

• Find the pivot (the smallest element) using a modified binary search.
• Once the pivot is known, the array is effectively two sorted subarrays: one from pivot to end, and one from start to pivot-1.
• Use standard binary search on the appropriate subarray based on where the target lies.

Alternatively, we can perform binary search directly without explicitly finding the pivot by checking which half of the array is sorted and then deciding where to search.

Direct Binary Search on Rotated Array

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

# Example
print(search_rotated([4,5,6,7,0,1,2], 0))  # Output: 4

Finding the Pivot First

def find_pivot(nums):
    low, high = 0, len(nums) - 1
    while low < high:
        mid = (low + high) // 2
        if nums[mid] > nums[high]:
            low = mid + 1
        else:
            high = mid
    return low

def search_with_pivot(nums, target):
    pivot = find_pivot(nums)
    n = len(nums)
    # binary search on the appropriate subarray
    if target <= nums[-1]:
        # search in right part [pivot .. n-1]
        low, high = pivot, n - 1
    else:
        # search in left part [0 .. pivot-1]
        low, high = 0, pivot - 1
    while low <= high:
        mid = (low + high) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

Complexity

Applications

• Searching in circularly sorted arrays, common in databases and file systems.
• Algorithms for finding the minimum element in a rotated sorted array.
• Variants of binary search problems in coding interviews.