Summary of "BS-6. Minimum in Rotated Sorted Array"

Summary of “BS-6. Minimum in Rotated Sorted Array”

This video is part of a binary search playlist from Striver’s A to Z DSA course. It focuses on solving the problem of finding the minimum element in a rotated sorted array using an optimized binary search approach.

Main Ideas and Concepts

Problem Statement: Given a rotated sorted array (an originally sorted array rotated at some pivot), find the minimum element in the array.
Rotated Sorted Array: Example: Original sorted array [0,1,2,4,5,6,7] rotated at a pivot index results in [4,5,6,7,0,1,2]. The minimum element here is 0.
Brute Force Approach:
- Traverse the entire array to find the minimum element.
- Time complexity: O(n).
- Not efficient and not preferred in interviews.
Binary Search Approach:
- Use the property of the rotated sorted array to apply binary search and reduce time complexity to O(log n).
- Key insight: One half of the array (left or right) is always sorted.
- Identify the sorted half to decide which half to eliminate.
Identifying Sorted Half:
- Compare values at low, mid, and high indices.
- If arr[low] <= arr[mid], left half is sorted.
- Otherwise, right half is sorted.
Finding the Minimum:
- The minimum element lies in the unsorted half because the rotation pivot causes one half to be unsorted.
- However, the sorted half may sometimes contain the minimum (especially in edge cases), so careful checks are needed.
Algorithm Steps:
1. Initialize low = 0, high = n-1, and answer = INT_MAX (or a very large number).
2. While low <= high:
  - Calculate mid = low + (high - low) / 2.
  - If left half (arr[low] to arr[mid]) is sorted:
    - Update answer = min(answer, arr[low]) (minimum in the sorted half is the first element).
    - Eliminate left half by setting low = mid + 1.
  - Else (right half is sorted):
    - Update answer = min(answer, arr[mid]).
    - Eliminate right half by setting high = mid - 1.
3. Return answer as the minimum element.
Optimization:
- If the entire current search space is sorted (arr[low] <= arr[high]), then arr[low] is the minimum.
- Update answer and break early from the loop to improve efficiency.
Time Complexity:
- O(log n) for arrays with unique elements.
- Handling duplicates is more complex and left as homework.
Coding Style:
- The instructor prefers consistent binary search code patterns (low = mid + 1, high = mid - 1) rather than inclusive mid assignments (low = mid or high = mid).

Detailed Methodology / Instructions

Input: Rotated sorted array arr of size n.
Output: Minimum element in the array.
Steps:

plaintext low = 0 high = n - 1 answer = INT_MAX

While low <= high:

1. Calculate `mid = low + (high - low) // 2`.  
2. If `arr[low] <= arr[high]`:  
      - The subarray is sorted, update `answer = min(answer, arr[low])` and break.  
3. Else if `arr[low] <= arr[mid]`:  
      - Left half is sorted.  
      - Update `answer = min(answer, arr[low])`.  
      - Eliminate left half: `low = mid + 1`.  
4. Else:  
      - Right half is sorted.  
      - Update `answer = min(answer, arr[mid])`.  
      - Eliminate right half: `high = mid - 1`.

Return answer.

Examples Discussed

Rotated array with pivot causing left half sorted and right half unsorted.
Rotated array where right half is sorted and contains minimum.
Edge cases with small arrays like [1, 2] or [2, 1].
Example showing both halves sorted after crossing the rotation point, triggering the optimization.

Additional Notes

The instructor references previous videos for foundational concepts on rotated sorted arrays and binary search.
The code is implemented in C++ and also available in Java, Python, and JavaScript in the course notes.
Homework suggested: Handling duplicates in rotated sorted arrays.
Encouragement to maintain consistent binary search coding style for clarity.

Speakers / Sources Featured

Primary Speaker: The channel instructor (unnamed), presumably Striver or a related educator from the Striver’s A to Z DSA course.

This summary captures the problem explanation, the binary search approach to solve it, optimization tips, and coding methodology emphasized by the instructor.