求n个元素的最小值二分算法
时间: 2023-07-26 11:08:03 浏览: 43
二分法可以用来在一个有序数组中查找某个元素,但是要找最小值,需要稍微修改一下。
具体做法是,假设有一个有序数组 `arr`,我们要找到其中的最小值。我们可以将数组的第一个元素作为左端点 `l`,最后一个元素作为右端点 `r`。然后,我们可以不断用二分法找到数组中间位置 `mid`,如果 `mid` 比 `r` 小,则说明最小值在左半边,可以将 `r` 更新为 `mid`;否则,最小值在右半边,可以将 `l` 更新为 `mid + 1`。最终,当 `l` 和 `r` 相等时,就找到了最小值,即 `arr[l]`。
以下是用 C++ 实现的最小值二分算法。
```c++
#include <iostream>
#include <vector>
using namespace std;
int findMin(vector<int>& nums) {
int l = 0, r = nums.size() - 1;
while (l < r) {
int mid = (l + r) / 2;
if (nums[mid] < nums[r]) {
r = mid;
} else {
l = mid + 1;
}
}
return nums[l];
}
int main() {
vector<int> nums = {4, 5, 6, 7, 0, 1, 2};
cout << findMin(nums) << endl; // 输出 0
return 0;
}
```