在C ++中的旋转排序数组II中查找最小值
假设我们有一个已排序的数组，现在它已在某个轴上旋转了。枢轴以前未知。我们必须从该数组中找到最小的元素。因此，如果数组类似于[4,5,5,5,6,8,2,3,4]，则最小元素为2。
为了解决这个问题，我们将遵循以下步骤-
定义一个称为的方法search()，这需要arr，low和high
如果低=高，则返回arr[低]
中：=低+（高–低）/2
ans：=inf
如果arr[low]<arr[mid]，则ans：=minofarr[low]andsearch(arr,mid,high)
否则，当arr[high]>arr[mid]时，则ans：=minofarr[mid]并搜索(arr,low,mid)
否则，当arr[low]=arr[mid]时，则ans：=minofarr[low]并搜索（arr，低+1，高）
否则，当arr[high]=arr[mid]时，则ans：=minofarr[high]并搜索(arr,low,high-1)
返回ans
从主方法调用solve（nums，0，nums–1）
示例
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int search(vector <int>& arr, int low, int high){
if(low == high){
return arr[low];
}
int mid = low + (high - low) / 2;
int ans = INT_MAX;
if(arr[low] < arr[mid]){
ans = min(arr[low], search(arr, mid, high));
}
else if (arr[high] > arr[mid]){
ans = min(arr[mid], search(arr, low, mid));
}
else if(arr[low] == arr[mid]){
ans = min(arr[low], search(arr, low + 1, high));
}
else if(arr[high] == arr[mid]){
ans = min(arr[high], search(arr, low, high - 1));
}
return ans;
}
int findMin(vector<int>& nums) {
return search(nums, 0, nums.size() - 1);
}
};
main(){
Solution ob;
vector<int> v = {4,5,5,5,6,8,2,3,4};
cout <<(ob.findMin(v));
}输入项
[4,5,5,5,6,8,2,3,4]
输出结果
2