Problem Statement:

Imagine you’re in a game show where you have to find the smallest number in a sorted array that has been rotated at some unknown pivot. Sounds easy? Well, let’s throw in some twists! You’re given an ascending sorted array, but someone sneakily rotated it. Your job is to find the minimum element in O(log n) time. The array does not contain duplicates. Example:
📌 Input: [4, 5, 6, 7, 0, 1, 2]
📌 Output: 0 Explanation: The original sorted array might have been [0, 1, 2, 4, 5, 6, 7], but it was rotated at index 3. The smallest number (0) is what we’re looking for.

Brute Force Approach

The simplest way to find the minimum is to scan the array from start to end and return the smallest element. Code Implementation (Brute Force)

public int findMinBruteForce(int[] nums) {
    int min = Integer.MAX_VALUE;
    for (int num : nums) {
        if (num < min) {
            min = num;
        }
    }
    return min;
}

⏳ Time Complexity: O(n) (because we scan the entire array).
🧠 Space Complexity: O(1) (we only use a single variable to track the min). Why this is bad?
While this approach works, it’s painfully slow for large inputs. We can do much better using binary search!

Optimized Approach – Binary Search to the Rescue!

Since the array was originally sorted, but rotated, we can use binary search to locate the smallest element in O(log n)time.

The Thought Process 🧠

1. Identify the middle element.
2. Check which half is unsorted.
   • If mid is greater than right, the minimum is somewhere in the right half.
   • Else, the minimum is somewhere in the left half.
3. Repeat until you find the minimum element! Code Implementation (Binary Search Approach)

public int findMin(int[] nums) {
    int left = 0, right = nums.length - 1;

    while (left < right) {
        int mid = left + (right - left) / 2;
        // If mid element is greater than right, min must be in right half
        if (nums[mid] > nums[right]) {
            left = mid + 1;
        } else {
            // Otherwise, min is in left half (including mid)
            right = mid;
        }
    }
    return nums[left]; // Left and right converge to min element
}

⏳ Time Complexity: O(log n) (binary search reduces the problem size by half each time).
🧠 Space Complexity: O(1) (we just use a few variables).

Step-by-Step Walkthrough (Example)

Let’s say we have the input: nums = [4, 5, 6, 7, 0, 1, 2] Iteration 1:

• left = 0, right = 6 → mid = 3 (element 7)
• nums[mid] > nums[right] → 7 > 2 → Search right half
• New range: left = 4, right = 6 Iteration 2:
• left = 4, right = 6 → mid = 5 (element 1)
• nums[mid] > nums[right] → 1 > 2 → Search left half
• New range: left = 4, right = 5 Iteration 3:
• left = 4, right = 5 → mid = 4 (element 0)
• nums[mid] <= nums[right] → 0 ≤ 1 → Search left half
• New range: left = 4, right = 4 Found it! 🎯 When left == right, we found the minimum → 0

Final Thoughts

Using binary search, we cracked the problem in O(log n) time instead of O(n). The key realization is binary search is great for doing searches in sorted arrays even if there is a twist. Happy leetcoding!🚀