LeetCode 153. Find Minimum in Rotated Sorted Array

Today we're going to solve LeetCode 153. Find Minimum in Rotated Sorted Array

| Problem description

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

[4,5,6,7,0,1,2] if it was rotated 4 times. [0,1,2,4,5,6,7] if it was rotated 7 times. Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

Examples:

Example 1:

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

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.
Example 3:

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

| Concept

We can use binary to solve this question. Different from normal binary search, we need to add an additional if else condition to check how to move the left/right index.

Hint:

If the element at the middle of the vector is higher than at the left, the vector from the left to the middle is sorted.

Therefore, we can add this additional conditional check to our binary search algorithm,

| Analyzed complexity:

Time complexity: O(Log(N))
Space complexity: O(1)

| Code

class Solution {
  public:
      int findMin(vector<int>& nums) {

          int ans = INT_MAX;
          int left = 0;
          int right = nums.size() - 1;

          while (left <= right) {
              int mid = left + (right - left) / 2;
              
              if (nums[mid] >= nums[left]) {
                  ans = min(nums[left], ans);
                  left = mid + 1;
              } else {
                  ans = min(nums[mid], ans);
                  right = mid - 1;
              }
          }
          return ans;
      }
  };