二分

思想很容易理解，但是写起来可能就会出现很多问题，下面给出一套完整的模板：

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> nums;

// 自定义 upper_bound，返回 <= target 的最大下标
int my_upper_bound(int target) {
    int l = -1;
    int r = n;
    while (l + 1 != r) {
        int mid = (l + r) / 2;
        if (nums[mid] <= target) {
            l = mid;
        } else {
            r = mid;
        }
    }
    return l;
}

// 自定义 lower_bound，返回 >= target 的最小下标
int my_lower_bound(int target) {
    int l = -1;
    int r = n;
    while (l + 1 != r) {
        int mid = (l + r) / 2;
        if (nums[mid] >= target) {
            r = mid;
        } else {
            l = mid;
        }
    }
    return r;
}

int main() {
    // 初始化有序数组
    nums = {1, 3, 3, 5, 7, 9, 9, 9, 15};
    n = nums.size();

    int target = 9;
    int lo = my_lower_bound(target);
    int up = my_upper_bound(target);

    cout << "Target: " << target << endl;
    cout << "Lower bound index: " << lo << ", Value: " << (lo < n ? nums[lo] : -1) << endl;
    cout << "Upper bound index: " << up << ", Value: " << (up >= 0 ? nums[up] : -1) << endl;

    return 0;
}