设 a[o:n-1]是已排好序的数组。请改写二分搜索算法，使得当搜索元素不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。用C++写

以下是改写后的二分搜索算法，返回一个pair，分别表示小于x的最大元素位置和大于x的最小元素位置。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

pair<int, int> binary_search(vector<int>& nums, int target) {
    int n = nums.size();
    int left = 0, right = n - 1;
    int lower = -1, upper = n;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return make_pair(mid, mid);
        } else if (nums[mid] < target) {
            lower = mid;
            left = mid + 1;
        } else {
            upper = mid;
            right = mid - 1;
        }
    }
    return make_pair(lower, upper);
}

int main() {
    vector<int> nums = {1, 3, 5, 7, 9};
    int target1 = 4;
    int target2 = 6;
    auto res1 = binary_search(nums, target1);
    auto res2 = binary_search(nums, target2);
    cout << "target1: " << res1.first << ", " << res1.second << endl;
    cout << "target2: " << res2.first << ", " << res2.second << endl;
    return 0;
}

输出结果为：

target1: 1, 2
target2: 2, 3

其中，target1不在数组中，返回的是小于的最大元素位置1和大于的最小元素位置2；target2在数组中，返回的是在数组中的位置2。