THE LIST WAS SORTED THEN ROTATED. COMPARE THE MIDDLE TO THE RIGHT EDGE: IF MID IS BIGGER THE SMALLEST VALUE LIES RIGHT, ELSE IT IS HERE OR LEFT. EACH PROBE HALVES WHAT IS LEFT.
A ROTATION LEAVES ONE DROP WHERE THE SMALLEST VALUE SITS. THE RIGHT EDGE SAYS WHICH SIDE HOLDS IT: A MIDDLE OVER THE EDGE MEANS THE DROP IS FURTHER RIGHT, OTHERWISE IT IS HERE OR LEFT. ONE COMPARISON DROPS HALF THE RANGE.
ONE PROBE AT A TIME. BLUE LO AND PINK HI FENCE THE LIVE RANGE, GREEN MID IS THE GUESS, PINK EDGE IS THE RIGHT WALL IT IS MEASURED AGAINST. THE DIMMED TILES ARE RULED OUT. THE GOLD TILE IS THE MINIMUM.
1def findMin(nums):2 l = 03 r = len(nums) - 14 while l < r:5 m = l + (r - l) // 26 if nums[m] > nums[r]:7 l = m + 18 else:9 r = m10 return nums[r]
EACH PROBE DROPS HALF THE RANGE, SO THE LIST IS EXHAUSTED IN ABOUT LOG N STEPS.
JUST THREE INDICES: LO, HI, MID.