LeetCode 153. Find Minimum in Rotated Sorted Array I

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description/

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

 Example 1:

Input: nums = [3,4,5,1,2]

Output: 1

Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2:

Input: nums = [4,5,6,7,0,1,2]

Output: 0

Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3:

Input: nums = [11,13,15,17]

Output: 11

Explanation: The original array was [11,13,15,17] and it was rotated 4 times. 

{4, 5, 6, 7, 0, 1, 2, 3}

{7, 8, 0, 1, 2, 3, 4, 5, 6}

{4, 5, 1, 2, 3}

package LeetCode.binarySearch;

public class LT153_SearchInRotatedSortedArray3 {

    public static void main(String[] args) {
        int[] arr = new int[]{4, 5, 6, 7, 0, 1, 2, 3};
        arr = new int[]{4, 5, 1, 2, 3};
        arr = new int[]{4, 5, 6, 0, 1, 2};

        System.out.println(search(arr));

    }

    public static int search(int[] nums) {
        int low = 0;                       // O(1) time & space
        int high = nums.length - 1;        // O(1) time & space
        int min = Integer.MAX_VALUE;       // O(1) time & space

        // Loop will run at most O(log n) times since we halve the search space each iteration
        while (low <= high) {              // O(log n) time
            int mid = low + (high - low) / 2;  // O(1) time & space

            // if search space is already sorted
            // then always arr[low] will be smaller
            if (nums[low] <= nums[high]) {
                min = Math.min(min, nums[low]);
                break;
            }

            // Left half is sorted
            if (nums[low] <= nums[mid]) { // O(1) time
                // get minimum
                min = Math.min(min, nums[low]); // O(1) time

                // eliminate left half
                low = mid + 1;            // O(1) time & space
            }
            // Right half is sorted
            else {
                // get minimum
                min = Math.min(min, nums[mid]); // O(1) time

                // eliminate right half
                high = mid - 1;           // O(1) time & space
            }
        }

        return min;                       // O(1) time & space
    }
}

Time Complexity (TC):

Best Case: O(1) — minimum found immediately

Average Case: O(log n) — binary search halving the array

Worst Case: O(log n) — rotated array causes full binary search traversal
Space Complexity (SC):

Best/Average/Worst Case: O(1) — only constant extra space used