### View *Find Minimum in Rotated Sorted Array* on LeetCode

## Statistics

**Time Complexity**

O(log n) - We are performing a modified version of binary search, and when binary search is performed on a sorted array, the time complexity is O(log n).

**Space Complexity**

O(1) - The number of variables created is independent of n, resulting in the O(1) space complexity.

## Explanation

Before performing a binary search, we must initialize our left and right variables; `l`

to “point” at element 0 and `r`

to “point” at the last element.

We start and continue the `while`

loop until `l`

is larger than `r.`

Inside the loop, we initialize `m`

to the middle of `l`

and `r`

.

If the number at

`m`

is larger than the number at`r`

, then`m`

is inside of the pivoted portion of the list, meaning there will not be any elements less than the one at`m`

to the left of element`m`

. Therefore, we must search the right side of the list, and we do this by`l = m + 1`

.If the number at

`m`

does not meet the previous condition, then we are in the sorted portion of the list and can move our right pointer to the left,`r = m`

.

Once our `while`

loop exits, we have found the minimum element at our right pointer `r`

and can simply return it.

## Algorithm Description

**Binary Search -** A search algorithm that repeatedly halves the search interval until the target variable is found at the middle index.

**Visual Examples**

Binary search being performed on an array that contains the target, click to view

Binary search being performed on an array that does **not** contain the target, click to view

## Solution

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
def findMin(self, nums: List[int]) -> int:
l = 0
r = len(nums) - 1
while l < r:
m = (l+r)//2
if nums[m] > nums[r]: l = m + 1
else: r = m
return nums[r]