Summary of "BS-4. Search Element in Rotated Sorted Array - I"

Summary of “BS-4. Search Element in Rotated Sorted Array - I”

This video tutorial is part of a binary search series from the Striver’s A to Z DSA course. It focuses on solving the problem of searching for an element in a rotated sorted array with unique elements. The instructor explains the problem, the challenges, and a detailed approach to efficiently solve it using a modified binary search.

Main Ideas and Concepts

Rotated Sorted Array Definition A rotated sorted array is formed by taking a sorted array and rotating it at some pivot point. For example, the sorted array [1, 2, 3, 4, 5] rotated at 3 becomes [4, 5, 1, 2, 3].
Problem Statement Given a rotated sorted array with unique elements, find the index of a target element. If the target is not found, return -1.
Naive Approach
- Use linear search to scan the entire array.
- Time complexity: O(n) in the worst case.
Optimized Approach (Binary Search)
- Since the array is partially sorted, binary search can be adapted to solve this efficiently in O(log n) time.
- Key challenge: Unlike a fully sorted array, one half of the rotated array might not be sorted, so you cannot directly eliminate half the array based on a simple comparison.

Detailed Methodology / Steps to Solve the Problem

Initialize Pointers
- low = 0
- high = n - 1 (where n is the size of the array)
While low <= high:
- Calculate mid = (low + high) // 2
- If arr[mid] == target, return mid immediately.
Identify the Sorted Half
- Check if the left half [low ... mid] is sorted:
  - If arr[low] <= arr[mid], then left half is sorted.
  - Else, the right half [mid ... high] is sorted.
Decide Which Half to Eliminate
- If the left half is sorted:
  - Check if the target lies between arr[low] and arr[mid] (inclusive).
    - If yes, eliminate the right half by setting high = mid - 1.
    - Else, eliminate the left half by setting low = mid + 1.
- If the right half is sorted:
  - Check if the target lies between arr[mid] and arr[high] (inclusive).
    - If yes, eliminate the left half by setting low = mid + 1.
    - Else, eliminate the right half by setting high = mid - 1.
Repeat the process until low exceeds high.
- If the target is not found, return -1.

Important Points & Insights

You cannot assume which half to eliminate without checking which half is sorted first.
Either the left half or the right half is guaranteed to be sorted due to the nature of rotation.
The binary search elimination step depends on the sorted half and whether the target lies within that half’s range.
This approach reduces the search space logarithmically, achieving O(log n) time complexity.

Code Structure (Pseudocode)

def search_rotated_array(arr, target):
    low, high = 0, len(arr) - 1

    while low <= high:
        mid = (low + high) // 2

        if arr[mid] == target:
            return mid

        # Check if left half is sorted
        if arr[low] <= arr[mid]:
            # Target in left half?
            if arr[low] <= target < arr[mid]:
                high = mid - 1
            else:
                low = mid + 1
        else:
            # Right half is sorted
            if arr[mid] < target <= arr[high]:
                low = mid + 1
            else:
                high = mid - 1

    return -1

Time Complexity

The time complexity of this approach is O(log n) due to the binary search mechanism.

Summary of the Problem-Solving Approach

Understand the rotated sorted array structure.
Use binary search but adapt it by first identifying the sorted half.
Eliminate the half where the target cannot lie based on sorted half and target range.
Continue until the target is found or search space is exhausted.

Speakers / Sources Featured

Primary Speaker: The instructor hosting the channel (name not explicitly mentioned).
Reference to Striver’s A to Z DSA course as the source of the problem and methodology.

This summary captures the key concepts, the problem-solving strategy, and the binary search adaptation needed to solve the “Search in Rotated Sorted Array” problem efficiently.