Python Program to Find Minimum in Rotated Sorted Array

Use a binary search approach with low and high pointers to find the minimum in a rotated sorted array by checking the middle element and adjusting pointers until the minimum is found.

Examples

Input[3, 4, 5, 1, 2]

Output1

Input[4, 5, 6, 7, 0, 1, 2]

Output0

Input[1]

Output1

How to Think About It

To find the minimum in a rotated sorted array, think of the array as two sorted parts joined together. The minimum is the point where the order breaks. Use two pointers at the start and end, check the middle value, and decide which half to search next by comparing middle and end values until you find the smallest element.

Algorithm

1

Set low to 0 and high to the last index of the array.

2

While low is less than high:

3

Check the middle index between low and high.

4

If the middle element is greater than the element at high, move low to middle + 1.

5

Otherwise, move high to middle.

6

Return the element at low as the minimum.

Code

python

def find_min(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 nums[low]

# Example usage
arr = [4, 5, 6, 7, 0, 1, 2]
print(find_min(arr))

Output

0

Dry Run

Let's trace the example [4, 5, 6, 7, 0, 1, 2] through the code

1

Initialize pointers

low = 0, high = 6 (array length - 1)

2

First iteration

mid = (0 + 6) // 2 = 3, nums[mid] = 7, nums[high] = 2, since 7 > 2, set low = mid + 1 = 4

3

Second iteration

low = 4, high = 6, mid = (4 + 6) // 2 = 5, nums[mid] = 1, nums[high] = 2, since 1 <= 2, set high = mid = 5

4

Third iteration

low = 4, high = 5, mid = (4 + 5) // 2 = 4, nums[mid] = 0, nums[high] = 1, since 0 <= 1, set high = mid = 4

5

Loop ends

low = 4, high = 4, loop ends, minimum is nums[4] = 0

low	high	mid	nums[mid]	nums[high]	Action
0	6	3	7	2	low = mid + 1 = 4
4	6	5	1	2	high = mid = 5
4	5	4	0	1	high = mid = 4

Why This Works

Step 1: Why use binary search?

Because the array is sorted but rotated, binary search helps find the point where order breaks efficiently instead of checking all elements.

Step 2: Comparing middle and high elements

If the middle element is greater than the high element, the minimum must be to the right, so move low up; otherwise, it is to the left or at mid.

Step 3: Loop ends when low meets high

When low equals high, it points to the smallest element, which is the minimum in the rotated array.

Alternative Approaches

Linear search

python

def find_min_linear(nums):
    min_val = nums[0]
    for num in nums:
        if num < min_val:
            min_val = num
    return min_val

print(find_min_linear([4,5,6,7,0,1,2]))

Simple but slower O(n) time, good for small arrays or when binary search is not needed.

Using built-in min() function

python

def find_min_builtin(nums):
    return min(nums)

print(find_min_builtin([4,5,6,7,0,1,2]))

Easiest to write but also O(n) time, no binary search optimization.

Complexity: O(log n) time, O(1) space

Time Complexity

The binary search divides the search space in half each time, so it runs in O(log n) time.

Space Complexity

Only a few variables are used for pointers and indices, so space is O(1).

Which Approach is Fastest?

Binary search is fastest for large arrays due to O(log n) time, while linear search and built-in min() are O(n).

Approach	Time	Space	Best For
Binary Search	O(log n)	O(1)	Large rotated sorted arrays
Linear Search	O(n)	O(1)	Small arrays or unsorted data
Built-in min()	O(n)	O(1)	Quick coding, small arrays