利用二分查找,找出数列中最小值的位置。注意:数据可能重复。如果最小值出现了多次,找出该最小值最后一次出现的位置 用c++的语言。
时间: 2024-10-24 21:06:37 浏览: 15
在C++中,我们可以利用二分查找的思想找到一个有序数组中最小值的最后一个出现位置。首先,我们确认数组是否已经排序,然后从数组的最后一个元素开始向前遍历,同时维护两个指针,一个用于查找最小值,另一个用于跟踪其最近一次出现的位置。
```cpp
#include <vector>
using namespace std;
int findLastMin(vector<int>& nums) {
if (nums.empty()) return -1; // 如果数组为空,返回-1
// 验证数组已排序
for (size_t i = 0; i < nums.size() - 1; ++i) {
if (nums[i] > nums[i + 1]) {
cout << "Array is not sorted. Binary search cannot be applied.\n";
return -1;
}
}
int left = 0, right = nums.size() - 1, last_min_index = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == nums[last_min_index]) {
last_min_index = mid;
// 右侧继续查找,因为可能存在更小的值在右侧
right = mid - 1;
} else if (nums[mid] < nums[last_min_index]) {
last_min_index = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return last_min_index;
}
// 示例用法
int main() {
vector<int> nums = {1, 2, 3, 1, 4, 1, 5};
int result = findLastMin(nums);
if (result != -1)
cout << "The index of the last occurrence of the minimum value is: " << result << endl;
return 0;
}
阅读全文