C++의 회전 정렬 배열에서 최소값 찾기

<시간/>

배열이 있고 정렬되어 있다고 가정하고 배열이 우리에게 알려지지 않은 일부 피벗에서 회전한다고 가정합니다. 따라서 회전된 배열에서 최소값을 찾아야 합니다. 따라서 배열이 [3,4,5,1,2]와 같으면 출력은 1이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

low :=0 및 high :=배열의 마지막 인덱스, n :=배열의 크기, ans :=무한대
낮은 동안 <=높음
- 중간 :=낮음 + (높음 - 낮음)/2
- arr[low]
- arr[high]> arr[mid]이면 ans :=ans 및 arr[mid]의 최소값, high :=mid – 1
- low =mid인 경우 ans :=ans 및 arr[low]의 최소값, low :=mid + 1
- else if high =mid, ans :=ans 및 arr[high]의 최소값, high :=mid - 1
반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#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]