在C ++中的旋转排序数组中查找最小值

  • Z时代
  • 2024-01-10
  • 分类：综合

假设有一个数组，并且已排序，请考虑将数组旋转到某个枢轴，这对我们来说是未知的。因此，我们必须从该旋转数组中找到最小值。因此，如果数组类似于[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

以上是 在C ++中的旋转排序数组中查找最小值 的全部内容， 来源链接： utcz.com/z/317099.html

回到顶部