Giả sử chúng ta có một mảng đã được sắp xếp, bây giờ nó được xoay ở một số trục. Trục xoay không được biết trước đây. Chúng ta phải tìm phần tử nhỏ nhất từ mảng đó. Vì vậy, nếu mảng giống như [4,5,5,5,6,8,2,3,4], thì phần tử tối thiểu là 2.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một phương thức được gọi là search (), phương thức này nhận arr, low và high
-
nếu low =high, thì trả về arr [low]
-
giữa:=low + (cao - thấp) / 2
-
ans:=inf
-
if arr [low]
-
ngược lại khi arr [high]> arr [mid] thì ans:=min of arr [mid] và search (arr, low, mid)
-
ngược lại khi arr [low] =arr [mid] thì ans:=min of arr [low] và search (arr, low + 1, high)
-
ngược lại khi arr [high] =arr [mid] thì ans:=min of arr [high] và search (arr, low, high - 1)
-
trả lại ans
-
Từ phương thức chính, cuộc gọi giải quyết (nums, 0, kích thước của nums - 1)
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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));
} Đầu vào
[4,5,5,5,6,8,2,3,4]
Đầu ra
2