C++ 从vector中间结合std::find与反向查找定位元素的实现问题

你代码不生效的核心原因是第一次反向查找得到down1后，直接将它作为第二次查找的起始位置，std::find从该位置开始匹配时，第一个符合==1条件的元素就是down1本身，不会向后继续找下一个符合条件的元素，需要将第二次查找的起始位置偏移1位，跳过已校验的元素。

同时你现有代码还存在两处逻辑错误：

• 上向查找的条件判断错误，你写的vec2[5] != up1 - vec1.begin()是拿vec2第5位的值和索引比较，和要求的vec2[i] != vec1[5]规则不符
• 缺失了第二向上查找的逻辑，无法覆盖你示例里第四步的查找场景

修正后完整代码 #

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

int main()
{
    std::vector<int> vec1 = {1, 0, 0, 1, 0, 3, 0, 0, 0, 0, 0, 1, 0, 1};
    std::vector<int> vec2 = {3, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0};
    const int start_idx = 5;
    const int target_val = vec1[start_idx];

    // 第一步：反向查找第一个1（起始点往左最近的1）
    auto down1 = std::find(vec1.rbegin() + (vec1.size() - start_idx), vec1.rend(), 1);
    if (down1 != vec1.rend()) {
        int i = std::distance(down1, vec1.rend()) - 1;
        if (vec2[i] != target_val) {
            std::cout << "First downsearch: found at index " << i << std::endl;
            return 0;
        }
    }

    // 第二步：正向查找第一个1（起始点往右最近的1）
    auto up1 = std::find(vec1.begin() + start_idx, vec1.end(), 1);
    if (up1 != vec1.end()) {
        int i = up1 - vec1.begin();
        if (vec2[i] != target_val) {
            std::cout << "First upsearch: found at index " << i << std::endl;
            return 0;
        }
    }

    // 第三步：反向查找第二个1（跳过第一个已校验的1）
    auto down2 = std::find(down1 + 1, vec1.rend(), 1);
    if (down2 != vec1.rend()) {
        int i = std::distance(down2, vec1.rend()) - 1;
        if (vec2[i] != target_val) {
            std::cout << "Second downsearch: found at index " << i << std::endl;
            return 0;
        }
    }

    // 第四步：正向查找第二个1（跳过第一个已校验的1）
    auto up2 = std::find(up1 + 1, vec1.end(), 1);
    if (up2 != vec1.end()) {
        int i = up2 - vec1.begin();
        if (vec2[i] != target_val) {
            std::cout << "Second upsearch: found at index " << i << std::endl;
            return 0;
        }
    }

    std::cout << "No matched element found" << std::endl;
    return 0;
}

补充说明 #

std::find的底层实现就是连续顺序遍历，和你手写while循环的性能没有差异，编译器开启优化后二者生成的汇编指令几乎完全一致，完全可以满足你99%近邻查找、1%远距离查找的性能需求。

内容的提问来源于stack exchange，提问作者schlumpel