在C ++中的旋转排序数组中查找最小值
假设有一个数组，并且已排序，请考虑将数组旋转到某个枢轴，这对我们来说是未知的。因此，我们必须从该旋转数组中找到最小值。因此，如果数组类似于[3,4,5,1,2]，则输出将为1。
为了解决这个问题，我们将遵循以下步骤-
低：=0和高：=数组的最后一个索引，n：=数组的大小，ans：=无穷大
而低<=高
中：=低+（高-低）/2
如果arr[low]<arr[mid]，则ans：=ans和arr[low]的最小值，low：=中+1
否则，如果arr[high]>arr[mid]，则ans：=ans和arr[mid]的最小值，high：=中–1
否则，如果low=中，则ans：=ans和arr[low]的最小值，low：=中+1
否则，如果high=中，则ans：=ans和arr[high]的最小值，high：=中-1
返回ans
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int findMin(vector<int>& arr) {
int low = 0;
int high = arr.size() - 1;
int n = arr.size();
int ans = INT_MAX;
while(low <= high){
int mid = low + (high - low) / 2;
if(arr[low] < arr[mid]){
ans = min(ans, arr[low]);
low = mid + 1;
} else if(arr[high] > arr[mid]) {
ans = min(ans, arr[mid]);
high = mid - 1;
} else if(low == mid) {
ans = min(ans, arr[low]);
low = mid + 1;
} else if(high == mid) {
ans = min(ans, arr[high]);
high = mid - 1;
}
}
return ans;
}
};
main(){
Solution ob;
vector<int> v = {15,35,85,96,5,6,8,12};
cout << ob.findMin(v);
}输入项
[15,35,85,96,5,6,8,12]
输出结果
5