C++二分查找：找出能挪动冰箱的最小力量值

我将使用 C++ 语言编写一个程序，通过二分查找来找出能挪动冰箱的人里力量值最小的一个。 ### 代码思路 1. **输入数据**：读取人数、每个人的力量值和冰箱的重量。 2. **对力量值排序**：将所有力量值存储在一个数组中，并进行升序排序。 3. **二分查找**：在排序后的数组中进行二分查找，找到第一个大于等于冰箱重量的力量值。 ### 代码实现 ```cpp #include <iostream> #include <algorithm> #include <vector> using namespace std; // 二分查找函数 int binarySearch(vector<int>& arr, int target) { int left = 0, right = arr.size() - 1; int result = -1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] >= target) { result = arr[mid]; right = mid - 1; } else { left = mid + 1; } } return result; } int main() { int n; cin >> n; vector<int> powerValues(n); // 读取每个人的力量值 for (int i = 0; i < n; ++i) { cin >> powerValues[i]; } // 对力量值进行排序 sort(powerValues.begin(), powerValues.end()); int fridgeWeight; cin >> fridgeWeight; int minPower = binarySearch(powerValues, fridgeWeight); cout << minPower << endl; return 0; } ``` ### 代码解释 - **`binarySearch` 函数**：该函数接受一个已排序的整数向量 `arr` 和一个目标值 `target`，使用二分查找算法在数组中找到第一个大于等于 `target` 的元素。 - **`main` 函数**：首先读取人数 `n` 和每个人的力量值，将其存储在 `powerValues` 向量中并排序。接着读取冰箱的重量 `fridgeWeight`，调用 `binarySearch` 函数找到最小的能挪动冰箱的力量值并输出。 ### 复杂度分析 - **时间复杂度**：排序步骤的时间复杂度为 $O(n log n)$，二分查找的时间复杂度为 $O(log n)$，总体时间复杂度为 $O(n log n)$。 - **空间复杂度**：主要是存储力量值的数组，空间复杂度为 $O(n)$。 ######[AI问答 | 598点数解答 | 2026-05-31 14:17:24]