The Minimum in a Rotated Sorted Array

Prerequisites: 🎞️Check if an array is sorted and rotated, ⁉️Thought Experiment, Does an array need to be sorted to run Binary Search?

Question

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times.

Reframing the question + Intuition

1. We will build on the concepts we learned in 🎞️Check if an array is sorted and rotated, make sure to look at this question to clarify these concepts,
1. What a sorted and rotated array is?
2. Understand how rotating a sorted array gives us two halves/sorted arrays.
3. Identify where the minimum and maximum occur in a sorted and rotated array.
2. Initially, we might think that we can’t do better than linear time since the array is not sorted after rotation. But then we might remember a previous lesson ⁉️Thought Experiment, Does an array need to be sorted to run Binary Search? Where we discussed that doing a question in logarithmic doesn’t have to mean that there is a sorted-ness property in the array we are looking over but understanding how the elements’ location is relative to the target—how each value in the array can be separated into separate halves and where the target lies from that half to the left or to the right?

3. How can we still accomplish this in logarithmic time?
1. The prerequisites of Logarithmic time require us to have the array divided into halves and have a similar property in terms of where the target lies with respect to each half. Let's take a look at the nature of the question to see if we can identify halves and see where the target lies with respect to that half, and with each iteration, reduce that range.
4. In the question 🎞️Check if an array is sorted and rotated, we determined that rotating sorted array results in two sorted arrays/halves.

1. Values in the upper, rotated part will be greater than those in the lower, unrotated part, and vice versa.
2. The minimum is located at the border between these two arrays, or the first element in the unrotated lower half.
5. Where is the target(minimum) in terms of these two halves?
1. If we are in the rotated/upper half of a sorted array, regardless of our position (e.g. 5,6), the target(minimum) we are looking for will always be to the right.
2. If we are in the unrotated lower half, no matter where we are (i.e. 2, 3, or 4), the target (minimum) we are looking for will always be to the left. We can assume the target (minimum) to be in the lower half, and it will always be the first element in that half.
3. Now we have two halves and how the relationship between the two halves is represented in regards to the target.
6. We begin by dividing the array into two halves. We then alternate between these two halves to narrow down our search until we find the target (minimum). Since the target is always in the lower half and the lower half is to the right, and we are chopping values from the right side in that half, the last value we will chop from the lower half will be our target.

7. Seems easy enough, but not be to hasty how do we know what half we are in? If we landed upon a random number how can we tell what half we are in?
1. Let's say we end up on 6 how can we know what half of the array we are in? From the image we know it is in the top half, but how can we formalize that in logic so the computer can understand?

1. We know two things about the nature of the array:
1. All elements in the top half are greater than those in the lower half, and vice versa.
2. The last element in the array will always be in the lower half and will always be lower/smaller than any element in the upper half.
3. Therefore, if we end up at an element greater than the last element in the rotated and sorted array (also the last element in the lower half), we will know we are in the top part of the array.
2. Let's say we end up at 2. We are clearly in the lower half but how can we formalize that in logic so the computer can understand?

1. Similar to finding an element in the upper half, all elements in the lower half will be less than the last element in the array (also the last element in the lower half). Thus, if we end up at an element that is smaller than the last element in the array (including the last element in the lower half), we can be certain that we are in the lower part of the array.
Copy

1 < 4 (last element)
2 < 4 (last element)
3 < 4 (last element)
4 <= 4 (last element) # not just smaller but also equal will be in the lower half.

#LOGIC
inLowerHalf = nums[mid] <= nums[-1]

8. Coming full circle.
1. Lower half, target to the left, and discard all elements to the right.
2. The upper half, target to the right, discard all elements to the left
3. We know
1. The target(minimum) is in the lower half and is the first element in that half.
2. All elements in the lower half are to the right of the target (we can also assume that the target is also on the right side of itself)
3. Whenever we are in the lower half we know that the target(minimum) is to the left In our bid to move closer to the target we discard all elements to the right.
4. Since we have included(assumed) the minimum in the lower half and we are chopping elements from the right, the last element we will chop from that half will be our target(minimum).
9. If we consider our being in the lower half as True. The problem is reduced to finding 🔑Find the First True in a Sorted Boolean Array .

Implementation and Comparision

class Solution:

    def firstTrue(self, bools):

        (left, right) = (0, len(bools) - 1)
        possibleValue = -1

        while left <= right:

            mid = left + (right - left) // 2
						

					 # True
            if bools[mid]: 
                possibleValue = mid
                right = mid - 1
						
					# False
            else:
                left = mid + 1

        
				return possibleValue

class Solution:
    def findMin(self, nums):

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

        while left <= right:
            
            mid = left + (right - left) // 2


            #True
            inLowerHalf = nums[mid] <= nums[-1] # <--change here
            if inLowerHalf:
                possibleMin = mid
                right = mid - 1

            #False
            else:
                left = mid + 1
            
        # returning the value instead the index
        return nums[possibleMin] # <--change here

Sandbox—PythonTutor (Visualized)

Complexities

Time Complexity: O(log(n))

Space Complexity: O(1)

📐Understanding Time Complexity of OLog(N): Math + Intuition

Follow Up

1. Will having duplicate digits make a difference? What changes need to be made to the code?
2. Try to write a program to get the maximum in a sorted rotated array.