数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法学C++ 实现旋转排序数组中的最小值查找
假设有一个已排序的数组，该数组在某个未知的枢轴点进行了旋转。我们需要找到该旋转数组中的最小值。例如，如果数组为 [3,4,5,1,2]，则输出为 1。
为了解决这个问题，我们将遵循以下步骤：
- low := 0，high := 数组的最后一个索引，n := 数组的大小，ans := 无穷大
- 当 low <= high 时
- mid := low + (high - low)/2
- 如果 arr[low] < arr[mid]，则 ans := ans 和 arr[low] 中的最小值，low := mid + 1
- 否则，如果 arr[high] > arr[mid]，则 ans := ans 和 arr[mid] 中的最小值，high := mid – 1
- 否则，如果 low = mid，则 ans := ans 和 arr[low] 中的最小值，low := mid + 1
- 否则，如果 high = mid，则 ans := ans 和 arr[high] 中的最小值，high := mid - 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
更新于：2020年5月4日
浏览量：116
广告