find min rotated Algorithm

The find min rotated algorithm is an efficient method used to find the minimum element in a sorted and rotated array. In a sorted and rotated array, the elements are sorted in ascending order, and then some elements are shifted from the beginning to the end of the array. This algorithm takes advantage of the binary search technique, which has a time complexity of O(log n) to determine the minimum element in the array. To implement this algorithm, first, we initialize two pointers, low and high, to the beginning and end indices of the array. Then, we iteratively perform a binary search by finding the middle index and comparing the elements at the low, middle, and high indices. If the middle element is greater than the high index element, it means that the minimum element lies in the right half of the array, so we update the low pointer to middle + 1. However, if the middle element is smaller than the high index element, it indicates that the minimum element is in the left half of the array, so we update the high pointer to middle. We continue this process until the low pointer is equal to the high pointer, at which point we have found the minimum element in the sorted and rotated array.
/**
 * Find Minimum in Rotated Sorted Array
 * Suppose a sorted array is rotated at some pivot unknown to you beforehand.
 *
 * (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
 *
 * Find the minimum element.
 *
 * You may assume no duplicate exists in the array.
 */

#include <iostream>
#include <vector>

int findMin(std::vector<int>& nums) {
	int n = nums.size();
	if ( n == 1 ) {
		return nums[0];
	}
	if ( n == 2 ) {
		return ( nums[0] < nums[1] ? nums[0] : nums[1]);
	}
	int i = n - 1;
	while ( i > 0 && nums[i] > nums[i-1]) {
		--i;
	}
	return nums[i];
}


int main() {
	std::cout << "Vec:";
	std::vector<int> vec{ 4, 5, 6, 7, 0, 1, 2 };
	for ( auto v : vec ) {
		std::cout << v << " ";
	}
	std::cout << std::endl;
	std::cout << "Min in above vector: " << findMin(vec) << std::endl;
	return 0;
}

LANGUAGE:

DARK MODE: