Finding smallest element in a rotated sorted array

Given a sorted array arrof n distinct elements rotated at one point, find the smallest element.

Example Test Case 1

Array: 6 1 2 3 4 5
Output: 1
Explanation: The original sorted array was 1 2 3 4 5 6 and which was rotated by one place to form 6 1 2 3 4 5. The minimum element is 1.

Example Test Case 2

Array: 4 5 6 2 3
Output: 3

Solution

Since the array is sorted, we can use modified binary search to solve this problem.
The key idea is that since the array is rotated, it can be thought of as containing two parts :

1. Lower Part : This is the part from the point of rotation to the last element before the smallest element. example the part containing numbers 4 5 6 in the test case 2.
2. Upper Part: The part starting from smallest element upto the last element in the array. example the part containing 2 3 in test case 2.

When doing modified binary search, we decide the direction of search by checking whether we are in the lower part or upper part.
If we are in lower part, then we need to move upwards while searching for the smallest number.
If we are in the upper part, then we need to move downwards while searching for the smallest number.

To detect whether I am in lower or upper part of the array, I can compare arr[mid] with arr[0].

1. If arr[mid] >= arr[0] then it means that I am in the lower half of the array and I have to move upwards. Therefore, I will do low = mid + 1 and continue my search.
2. If arr[mid] < arr[0] then it means that I am in the upper half of the array and I have to move downwards. Therefore, I will do high = mid - 1 and continue my search as shown in the below implementation.

Implementation

#include <iostream>
#include <vector>
using namespace std;

int findMin(vector<int>& nums) {
  int lo = 0, hi = nums.size() - 1;
  int mid = lo + (hi - lo)/2;
  int minElement = nums[0];
  while (lo <= hi) {
    mid = lo + (hi - lo)/2;
    if (nums[mid] >= nums[0]) {
      lo = mid + 1;
    }
    else {
      minElement = min(minElement, nums[mid]);
      hi = mid - 1;
    }
  }
  return minElement;
}

int main() {
	vector<int> vec = {4, 5, 6, 2, 3};
	cout << findMin(vec) << "\n";
}

Time Complexity

Since this is just like a standard binary search, with minor modification the time complexity will still be O(log(n)).