THE LIST IS SORTED. CHECK THE MIDDLE: IF THE TARGET IS BIGGER, THROW AWAY THE LEFT HALF, IF SMALLER THE RIGHT. EACH PROBE HALVES WHAT IS LEFT.
SORTED MEANS THE MIDDLE SPLITS THE LIST INTO A SMALLER HALF AND A BIGGER HALF. ONE COMPARISON SAYS WHICH HALF HOLDS THE TARGET, SO THE OTHER HALF IS GONE.
ONE PROBE AT A TIME. BLUE LO AND PINK HI FENCE THE LIVE RANGE, GREEN MID IS THE GUESS. THE DIMMED TILES ARE RULED OUT. THE GOLD TILE IS THE ANSWER.
1def search(nums, target):2 l = 03 r = len(nums) - 14 while l <= r:5 m = l + (r - l) // 26 if nums[m] == target:7 return m8 elif nums[m] > target:9 r = m - 110 else:11 l = m + 112 return -1
EACH PROBE DROPS HALF THE RANGE, SO THE LIST IS EXHAUSTED IN ABOUT LOG N STEPS.
JUST THREE INDICES: LO, HI, MID.