Example 1: Input: [3,4,5,6,7,1,2] Output: 1
We shall use 2 pointers to solve this problem.
Below are steps how the solution works:
- Frist we check arr[start] < arr[end], then we return the arr[start] value.
- Else
- Compute the mid element
- If arr[mid] > arr[start], then we know that the rotation is in the second half.
- If arr[mid] < arr[start], then we know that the rotation is in the first half.
Solution in C++
#include<iostream> #include<vector> using namespace std; int find_min(vector<int> &arr) { int start = 0; int end = arr.size()-1; while (start < end) { if (arr[start]<arr[end]) return arr[start]; int mid = (start+end)/2; if (arr[mid] >= arr[start]) { start = mid+1; } else { end = mid; } } return arr[start]; } int main() { vector<int> arr; arr.push_back(3); arr.push_back(4); arr.push_back(5); arr.push_back(1); arr.push_back(2); int result = find_min(arr); cout<<"The smallest element is = "<<result<<endl; return 0; }
Output:
The smallest element is = 1