Problem

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

• [4,5,6,7,0,1,2] if it was rotated 4 times.
• [0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

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.

Brainstorming

Brute force

I think we should just ignore the info as to how many times an array is rotated since it is not explicitly told to us as an input. So there is no point of using that. What we can do is use the insight for rotated sorted arrays, which is , at any given point when we slice the array in 2 equal half’s , at least 1 half is always sorted

this works well for searching a target in the said array but here we don’t have a target , so how will the discard logic look like?

one thing we can do is have some logic of discarding a side that is smaller than the other one say we split the array at mid then we need some way to identify which of the sides that is nums[left:mid] or nums[mid:right] is the smaller side here one thing we can do is treat them as intervals with starts and ends but how do we gurantee which side is sorted and which is not if we assume that both sides will be sorted then it becomes slightly easy since we will know for sure that nums[left] will be <= nums[mid] and nums[mid will be <= nums[right]

if the above is true we can just have a check in the while loop where we do this if nums[mid-1] < nums[mid+1] the left interval’s end is smaller than right interval’s start that means we can be sure that the right will have all numbers larger than left intervals hence we can discard it we can use a clever trick where we assume the mid to be the smallest number in the current iterations and each discard we will update that with the current mid value using min(current_min, min_till_now) logic

nums = [3,4,5,1,2] 
# nums = [11,13,15,17]
left = 0
right = len(nums) -1

min_so_far = float('inf') # placeholder max value 

while left <= right: # this will run till left == right
	mid = (left + right) //2
	min_so_far = min(min_so_far, nums[mid])
	if nums[mid-1] <= nums[mid+1]: # left is smaller than right
		right = mid - 1 # move right
	else:
		left = mid + 1 # move left

print(min_so_far)

Optimal solution

Your Insights (All Correct):

1. Ignore Rotation Count: Correct. It’s irrelevant information designed to distract.
2. The Core Property: You nailed it. “at least 1 half is always sorted.” This is the fundamental property of a rotated sorted array that makes binary search possible.
3. The Goal: Find the minimum element, which is the “inflection point” where the rotation happens.
4. The “Discard Logic” Question: This is the central question you need to answer to build the algorithm.
5. Your “Clever Trick”: min_so_far = min(min_so_far, nums[mid]). This is an excellent idea and a key part of the solution. At every step, the mid element is a candidate for the minimum, so we should always check it.

Let’s Refine Your Discard Logic:

Your current logic is: if nums[mid-1] <= nums[mid+1]: right = mid - 1 This is a good thought, but it has some issues:

• It looks at neighbors (mid-1, mid+1), which can be tricky with edge cases (what if mid is 0 or len-1?).
• It doesn’t fully utilize the “one half is sorted” property.

Let’s use your core insight more directly. At mid, we need to figure out which half is sorted.

How do we know if the left half (nums[left] to nums[mid]) is the sorted half?

• In a normally sorted array, the first element is less than or equal to the last element.
• So, if nums[left] <= nums[mid], we know for a fact that the entire left portion of the array is sorted and looks like [left, ..., mid].

Now comes the critical decision. If the left half (left to mid) is sorted:

• What is the minimum value within this sorted half? It must be nums[left].
• We can update our min_so_far with nums[left].
• Now, where could the true overall minimum be? It could be nums[left], OR it could be somewhere in the unsorted right half. The inflection point must be in the unsorted part.
• So, if the left half is sorted, we should discard the left half and search the right half. How do you move the pointers to search the right half?

What if the left half is NOT sorted?

• If nums[left] > nums[mid], it means the “break” or “inflection point” must have happened somewhere between left and mid.
• This also implies that the right half (mid to right) must be the sorted portion.
• What is the minimum value within this sorted right half? It must be nums[mid].
• We can update our min_so_far with nums[mid].
• The true overall minimum must be in this unsorted left half. How do you move the pointers to search the left half?

(Prompt): Based on this refined logic, can you write the if/else block that checks if the left half is sorted (nums[left] <= nums[mid]) and then correctly moves the left or right pointer to discard the appropriate half? Remember to update min_so_far in each block.

Got it so the approach that atleast 1 half should be sorted is correct , we don’t need to assume that both are sorted we just need to use it , check if left is sorted if yes then the lowest value is in nums[left] if it is not that means the right is sorted which means the lowest value is nums[mid] based on this updated logic we can refine the old code

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

left = 0
right = len(nums) -1
min_so_far = float('inf')

while left <= right:
	mid = (left + right) //2
	if nums[left] <= nums[mid]: # is left half sorted
		min_so_far = min(min_so_far, nums[left]) # if yes then the lowest value will be stored in the left pointer
		right = mid -1 # move the right pointer backwards
	else: # it means the right half is sorted
		min_so_far = min(min_so_far, nums[mid]) # the minimum value in the righ th half will be stored at the index mind
		left = mid + 1 # move the left pointer forward
	
print(min_so_far)
		

oh so in any sorted part we know for a fact that the lowest value is either left or mid which we do assign and thats were the sorted part job is done, so there is no point continue searching in that section as its already sorted , we should then search in the other interesting unsorted part so the pointers movement will be flipped

nums = [3,4,5,1,2]
left = 0
right = len(nums) -1
min_so_far = float('inf')

while left <= right:
	mid = (left + right) //2
	if nums[left] <= nums[mid]: # is left half sorted?
		min_so_far = min(min_so_far, nums[left]) # the minimum of the left half is stored in the left pointer value
		# this were we flip the search in the opposite direction
		left = mid +1
	else: # if not that means right half is sorted 
		min_so_far = min(min_so_far, nums[mid])  # the minimum value in the righ t half will be stored at the index mind
		# this were we flip the search in the opposite direction
		right = mid -1
		
print(min_so_far)