Tìm tối thiểu trong Mảng được sắp xếp xoay vòng trong C ++

Giả sử có một mảng và được sắp xếp, hãy coi mảng đó được xoay tại một trục nào đó mà chúng ta chưa biết. Vì vậy, chúng ta phải tìm giá trị nhỏ nhất từ ​​mảng đã quay đó. Vì vậy, nếu mảng giống như [3,4,5,1,2], thì đầu ra sẽ là 1.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• low:=0 và high:=chỉ số cuối cùng của mảng, n:=kích thước của mảng, ans:=infinity
• trong khi thấp <=cao
  • giữa:=low + (cao - thấp) / 2
  • if arr [low]
  • else if arr [high]> arr [mid], then ans:=Minimum ans và arr [mid], high:=mid - 1
  • else if low =mid, then ans:=Minimum ans và arr [low], low:=mid + 1
  • else if high =mid, then ans:=Minimum ans and arr [high], high:=mid - 1
• trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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);
}

Đầu vào

[15,35,85,96,5,6,8,12]

Đầu ra

5