C++ 二分查找找最左 最右的 完整代码
时间: 2024-09-24 07:13:04 浏览: 27
在C++中,二分查找通常用于已排序数组中找到特定元素的位置,而寻找最左边和最右边满足条件的元素可以稍作修改。下面是一个简单的示例,假设我们有一个`vector<int>`类型的已排序数组,我们要找到第一个大于等于目标值的元素的索引(最左),以及最后一个小于等于目标值的元素的索引(最右)。这里假设数组下标从0开始。
```cpp
#include <vector>
#include <limits>
// Binary search to find the first index greater than or equal to target
int binarySearchLeft(const std::vector<int>& arr, int target) {
int left = 0;
int right = arr.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] >= target) {
right = mid - 1; // Search in the left half
} else {
left = mid + 1; // Search in the right half
}
}
return left; // If not found, left will be the first index after target
}
// Binary search to find the last index less than or equal to target
int binarySearchRight(const std::vector<int>& arr, int target) {
int left = 0;
int right = arr.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] <= target) {
left = mid + 1; // Search in the right half
} else {
right = mid - 1; // Search in the left half
}
}
return right; // If not found, right will be the first index before target
}
// Example usage
int main() {
std::vector<int> sorted_arr = {1, 3, 4, 6, 8, 9};
int target = 5;
int leftmost_index = binarySearchLeft(sorted_arr, target);
int rightmost_index = binarySearchRight(sorted_arr, target);
std::cout << "First element greater than or equal to " << target << ": " << sorted_arr[leftmost_index] << "\n";
std::cout << "Last element less than or equal to " << target << ": " << sorted_arr[rightmost_index] << "\n";
return 0;
}
```