problem:

<aside>

given a sorted + rotated array of unique elements return the min element in O(log n) time

[0,1,2,4,5,6,7] might become:

• [4,5,6,7,**0**,1,2] if it was rotated 4 times → index 4 is pivot + minimum
• [**0**,1,2,4,5,6,7] if it was rotated 7 times → index (7%7) = 0 is pivot + minimum </aside>

solution:

<aside>

• regardless of where the rotation point falls on array, at least one side will always be sorted when using binary search
• use binary search to find which half of the rotated sorted array contains the pivot, which is the minimum element.
• at each step, compare nums[mid] with nums[right]:
  • if nums[mid] > nums[right], the minimum must be in the right half
  • otherwise it is in the left half including mid
• the search space keeps shrinking until left == right, and that index is the minimum
• edge cases:
  • input array size 2, ex. [2, 1] → beware out of bounds indexing at nums[mid+or-1] when left=0 and right=len(nums)-1 </aside>

code:

• 1st attempt → fails input: [2,1]

		left, right = 0, len(nums) - 1

    # shrink [left, right] until one element remains
    # when left == right we found the minimum 
    while left < right:
        mid = (left + right) // 2

				# left half is sorted
				# mid falls in left half
        if nums[mid] > nums[right]:
		        # minimum and pivot must be in right half
            left = mid + 1
            
        # nums[mid] <= nums[right]
        # right half is sorted
        # mid falls in right half   
        else: 
		        # mid could be min so keep in range 
            right = mid
	
		# left == right -> minimum value found
    return nums[left]

complexity:

<aside>

• Time: O(log n) because each iteration cuts the search range roughly in half

  • Binary Search → the number of steps k required to reduce an array of size n down to a single element is the value that satisfies:

    $$ n/2^k = 1 => 2^k = n => k = log_2(n) $$

• Space: O(1) because it uses only a few pointers and no extra data structures </aside>

walkthrough:

input: nums = [4,5,6,7,0,1,2], left = 0, right = 6

while left < right:

output: nums[4] = 0