Find Minimum in Rotated Sorted Array

Binary search

• In a particular iteration, at nums[mid], we are either in the left sorted portion or the right sorted portion. In example, 1, left sorted portion would be 3, 4, 5. When this happens, we would want to move to the right sorted portion, because the right sorted portion has the lower numbered elements.
• If our nums[mid] is in the left sorted portion, i.e. nums[mid] >= nums[l], we would need to move to the right sorted portion, so we would update ans and set left pointer to mid + 1. The reason for greater than or equal is for an edge case where nums[mid] == nums[l] (i.e. only one element in current bounds)
• Whenever the above condition evaluates to False, it means we are in the right sorter portion, and hence need to move to the left sorted portion by updating right to mid - 1
  • For example, take 3, 4, 5, 1, 2. Our left is at 3, right is at 2, and mid is at 1. (Just an arbitrary example, the middle won't actually be at 1)
• The algorithm does not work if the left and right pointers point to a sorted portion of the array. This is why, whenever nums[l] < nums[r], we possibly update our answer and immediately return

Take note of two conditions:

• If nums[l] < nums[r]
  • This condition is possible two times in the array, one for the left sorted portion, and one for the right
  • This means the array is in sorted position, possible update our answer with leftmost value (as we're looking for the minimum) and break out of while loop
  • If this condition is true, it means one of two things is possible. Take the example [4, 5, 1, 2, 3]. Either we are in:
    • We are in right sorted portion of the array, i.e. 1, 2, 3. In which case the line return min(ans, nums[l]) will return 1 as the correct answer
    • We are in left sorted portion of the array, i.e. 4, 5. To get to this point, we have already seen the other right sorted portion, so again, the line return min(ans, nums[l]) will return 1 as the correct answer.
• Elif nums[m] >= nums[l]
  • This means our mid is currently in the left sorted portion of the array, which contains elements greater than the right sorted position, since the array has been rotated
  • Take first example
    • 3, 4, 5, 1, 2
    • l m r
    • Our mid is 5, our left is 3. Since the above condition evaluates to true, we are in left sorted portion of the rotated array. Hence, we need to search the right in the next iteration.
  • We need the greater than condition for the edge case where the mid == l
• If the above condition isn't true, we are in the right sorted portion, and we need to recur to the left