Space
Open
From Fieldwork
Scales
Archive
Use binary search.
The "specificity of the minimum" simplifies the problem because finding the minimum relies only on the relative order (topology) of the graph, whereas searching for a target relies on specific value containment.
class Solution:
def findMin(self, nums: List[int]) -> int:
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2
# If the middle element is greater than the rightmost element,
# the minimum value must be in the right half.
if nums[mid] > nums[right]:
left = mid + 1
# Otherwise, the minimum is either at mid or in the left half.
# We keep 'mid' in the search space.
else:
right = mid
# When the loop terminates, left == right, pointing to the minimum.
return nums[left]Practice bench
A private scratchpad for this reading. Nothing is sent or scored.
What is still unclear, or what would change the explanation?
Saved on this device · one draft per mode