第一次出现的位置（二分查找）

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;
    vector<int> v(n), a(m);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    for (int i = 0; i < m; i++) {
        cin >> a[i];
    }

    vector<int> result(m, -1); // 存储结果，初始化为 -1

    for (int i = 0; i < m; i++) {
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (v[mid] == a[i]) {
                right = mid - 1;
                result[i] = mid + 1;
            } else if (v[mid] < a[i]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
       
    }

    for (int i = 0; i < m; i++) {
        cout << result[i] << " ";
    }

    return 0;
}

while (left <= right)

为什么是 <= 而不是 <，在二分查找的过程中，如果目标值恰好在 left == right 的位置，则会漏掉这部分。

如果 v[mid] == a[i]：

继续左边查找，缩小右边界 right = mid - 1，确保找到目标值的第一次出现位置。

记录当前索引（mid + 1）为结果。（1-based 索引）

如果 v[mid] < a[i]：

目标值在右侧，更新左边界 left = mid + 1。

如果 v[mid] > a[i]：

目标值在左侧，更新右边界 right = mid - 1。

如果二分查找结束后 result[i] 仍然是 -1，说明 a[i] 不存在于 v。

原文地址：https://blog.csdn.net/Ct314/article/details/143898079

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！