find 查找

读完能做什么

• 能用 find 在一个区间里查出指定值的元素，并读出它的位置和值。
• 能为“找到”和“没找到”两种情况分别写出正确的处理代码。
• 能用 find_if 加一个判断函数，找出第一个满足条件的元素（比如第一个大于 4 的数）。
• 能说清 it - v.begin() 这种“算下标”的写法在什么容器上能用、在什么容器上不能用。

为什么需要它

数组里查一个值，标准写法是自己扫一遍：

int a[5] = {8, 3, 5, 3, 1};
int pos = -1;
for (int i = 0; i < 5; i++) {
    if (a[i] == 3) {          // 找到第一个等于 3 的位置
        pos = i;
        break;
    }
}

这段片段（省略了头文件和 main）本身没错，但每查一次就要重复一次，而且“没找到”要靠额外的 pos = -1 来表示；如果数据放在 vector、list 里，循环的写法又要跟着改。这种“从左往右找到第一个符合条件的元素”的动作在程序里出现得太频繁，标准库把它做成了函数，这就是 find 和 find_if。

它是什么

一句话：find(first, last, value) 从 first 开始往右扫，返回第一个等于 value 的元素的位置；如果整个区间里都没有这样的元素，就返回 last。

几个概念就地解释：

迭代器与区间 [first, last)。 迭代器是“指向容器中某个位置的游标”。两个迭代器可以表示一段连续的位置，写成左闭右开区间 [first, last)：包含 first 指向的元素，不包含 last 指向的元素。v.begin() 指向第一个元素，v.end() 表示最后一个元素后面一个位置（注意不是最后一个元素本身），所以 [v.begin(), v.end()) 正好是整个 vector。查找的范围也用这种写法描述，find(v.begin(), v.end(), 3) 就是“在整个 v 里找 3”。

位置不是值。 find 返回的是一个迭代器，它表示“在哪里”。想知道那里的值，要用 *it 取出（这叫解引用）；想把它当作下标用，要通过 it - v.begin() 换算。

== 决定“相等”。 find 判断“这个元素是不是要找的值”用的是 ==，v[i] == value 为真就算命中。所以它只能查“值等于某个给定值”的元素；要查“满足某个条件”的元素，得用 find_if。

find_if(first, last, pred)。 第三个参数 pred 是一个判断条件：一个对元素返回 bool 的函数（函数对象也可以）。从左往右对每个元素调用它，第一次返回 true 的那个元素就是结果；全都不满足时同样返回 last。pred 的具体写法见 比较规则与函数对象，本页用最普通的函数。

必须处理“没找到”。 返回 last 表示没找到，这个位置不能解引用。所以通用写法是先比较再使用。

查找是逐个比较，数据不需要有序。 find 从头走到尾，最多看 n 个元素，复杂度 O(n)。它不要求数据排好序；如果数据已经有序、还想查得更快，就要用二分查找（见 二分查找）。

最小可运行示例

用数据 [8, 3, 5, 3] 查两个值：查存在的 3，再查不存在的 9。

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

int main() {
    vector<int> v = {8, 3, 5, 3};

    auto it = find(v.begin(), v.end(), 3);      // 查找值 3
    if (it != v.end()) {
        cout << "查找 3：下标 " << (it - v.begin()) << "，值 = " << *it << '\n';
    } else {
        cout << "查找 3：未找到" << '\n';
    }

    auto miss = find(v.begin(), v.end(), 9);    // 查找值 9
    if (miss != v.end()) {
        cout << "查找 9：下标 " << (miss - v.begin()) << "，值 = " << *miss << '\n';
    } else {
        cout << "查找 9：未找到" << '\n';
    }
    return 0;
}

输出：

查找 3：下标 1，值 = 3
查找 9：未找到

逐行看：

• vector<int> v = {8, 3, 5, 3}; 四个元素，下标依次是 0、1、2、3。
• find(v.begin(), v.end(), 3) 在 [v.begin(), v.end()) 这个区间里找等于 3 的元素，返回第一个命中的位置。
• if (it != v.end()) 先判断“找到了没有”。只有找到了，it 指向的才是一个真实元素，才能解引用。
• it - v.begin() 是两个迭代器相减，得到“从区间开头数过来走了几个位置”，也就是下标。3 在下标 1，所以输出 1。
• *it 取出那个位置的元素，值是 3。
• 查 9 时整个区间都没有 9，miss 等于 v.end()，走 else 分支输出“未找到”。

一步步看变化

find 的扫描过程如下，两种结果各走一遍：

查找 3（存在，在下标 1）：

查找 9（不存在）：

数据里有两个 3，结果是下标 1 而不是下标 3：find 只返回第一个匹配的位置，找到就立刻停下。

逐项扩展核心操作

用 find_if 查找“满足条件的元素”

find 只能比较“是否相等”，find_if 则把判断权交给一个函数：

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

// 判断条件：这个数比 4 大吗？
bool biggerThan4(int x) {
    return x > 4;
}

// 判断条件：这个数比 100 大吗？
bool biggerThan100(int x) {
    return x > 100;
}

int main() {
    vector<int> v = {8, 3, 5, 3};

    auto it = find_if(v.begin(), v.end(), biggerThan4);
    if (it != v.end()) {
        cout << "第一个大于 4 的元素：" << *it << "（下标 " << (it - v.begin()) << "）" << '\n';
    } else {
        cout << "没有大于 4 的元素" << '\n';
    }

    auto none = find_if(v.begin(), v.end(), biggerThan100);
    cout << "有没有大于 100 的元素：" << (none == v.end() ? "没有" : "有") << '\n';
    return 0;
}

输出：

第一个大于 4 的元素：8（下标 0）
有没有大于 100 的元素：没有

• biggerThan4 是一个普通函数：接收一个元素，回答“它满足条件吗”。把函数名交给 find_if，算法就会从左往右对每个元素调用它一次。
• 第一个元素 8 就满足 8 > 4，所以立即命中，返回下标 0。
• 第二次查找的条件是“大于 100”，四个元素都不满足，返回 v.end()，判断结果打印成“没有”。

find 和 find_if 的分工可以这样记：

普通数组上也能用

find 需要的是“两个位置”，普通数组用首指针和尾后指针就能表示，返回值也变成指针：

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

int main() {
    int a[] = {10, 20, 30, 40};

    int* p = find(a, a + 4, 30);           // 数组用首指针和尾后指针表示区间
    if (p != a + 4) {
        cout << "数组中找到 " << *p << "，下标 = " << (p - a) << '\n';
    } else {
        cout << "数组中没有 30" << '\n';
    }

    int* q = find(a, a + 4, 50);
    cout << "数组中有没有 50：" << (q == a + 4 ? "没有" : "有") << '\n';
    return 0;
}

输出：

数组中找到 30，下标 = 2
数组中有没有 50：没有

a 是首元素的位置，a + 4 是尾后位置（数组有 4 个元素，下标 0 到 3）。判断“找到了没有”要比的是 a + 4，算下标用的是 p - a。这和 vector 上的 v.begin()、v.end()、it - v.begin() 是同一套写法，只是位置由指针表示。

选读：用 lambda 写判断条件

判断条件也可以直接写在调用处，不必单独定义一个函数。这种写法叫 lambda 表达式：[](int x) { return x % 2 == 0; } 意思是“临时定义一个接收 int、返回 bool 的函数”，方括号 [] 说明它不捕获外面的变量，小括号里是参数，花括号里是函数体。

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

int main() {
    vector<int> v = {7, 3, 5, 4, 6};

    // 选读：这里用 lambda 写条件，等价于一个返回 bool 的小函数
    auto it = find_if(v.begin(), v.end(), [](int x) { return x % 2 == 0; });

    if (it != v.end()) {
        cout << "第一个偶数：" << *it << "（下标 " << (it - v.begin()) << "）" << '\n';
    } else {
        cout << "没有偶数" << '\n';
    }
    return 0;
}

输出：

第一个偶数：4（下标 3）

7、3、5 都不是偶数，4 是第一个偶数，下标 3。第一次读不懂 [](int x) { ... } 也没关系，用普通函数写同样清楚；它的好处是“条件只在这一次用得上”时不用起名字。

选读：查自定义类型，需要自己定义“相等”

find 靠 == 判断相等。如果元素是自定义结构体，而类型本身没有定义 ==，就编译不过：

// 错误示例：结构体没有定义 ==，find 无法比较两个 Point，编译失败
#include <bits/stdc++.h>
using namespace std;

struct Point {
    int x;
    int y;
};

int main() {
    vector<Point> v = {{1, 2}, {3, 4}};
    auto it = find(v.begin(), v.end(), Point{3, 4});   // 编译错误
    return 0;
}

这段不能通过编译，报错大意是“没有匹配 operator==”。给 Point 补上“两个点什么时候算相等”的定义，find 就能用了：

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

struct Point {
    int x;
    int y;
};

// 自己定义两个 Point 什么时候算"相等"
bool operator==(const Point& a, const Point& b) {
    return a.x == b.x && a.y == b.y;
}

int main() {
    vector<Point> v = {{1, 2}, {3, 4}, {5, 6}};

    auto it = find(v.begin(), v.end(), Point{3, 4});
    if (it != v.end()) {
        cout << "找到点：(" << it->x << ", " << it->y << ")" << '\n';
    } else {
        cout << "没有点 (3, 4)" << '\n';
    }

    auto miss = find(v.begin(), v.end(), Point{9, 9});
    cout << "查找 (9, 9)：" << (miss == v.end() ? "未找到" : "找到") << '\n';
    return 0;
}

输出：

找到点：(3, 4)
查找 (9, 9)：未找到

bool operator==(const Point& a, const Point& b) 是在给 Point 定义“== 运算符的行为”，这样 Point{3, 4} == Point{3, 4} 才是一个合法的布尔表达式。（operator() 的类似写法见 比较规则与函数对象。）输出里的 it->x 是 (*it).x 的简写：先取出 it 指向的那个 Point，再访问它的成员 x。如果不想给类型定义 ==，也可以用 find_if 直接写条件，比如 [](const Point& p) { return p.x == 3 && p.y == 4; }。

什么时候选它、哪里容易错

只返回第一个匹配的位置。 数据里有两个 3，find(v.begin(), v.end(), 3) 给的是下标 1，不是“所有 3”。想找下一个，就从返回位置的下一个继续找：find(it + 1, v.end(), 3)。要统计全部出现次数，得自己循环。

解引用之前必须和 end() 比较。

// 错误示例：没有先和 end() 比较就解引用，读的是尾后位置
#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {8, 3, 5, 3};
    auto it = find(v.begin(), v.end(), 9);   // 9 不存在，it == v.end()
    cout << *it << '\n';                     // 解引用尾后位置是未定义行为
    return 0;
}

这段能编过，但结果是未定义的：it 等于 v.end()，指向的不是任何元素，*it 读出来的是什么完全没有保证。所以本页不给它写“运行结果”。正确做法永远是先 if (it != v.end()) 再解引用。

算下标要看迭代器种类。 it - v.begin() 要求迭代器支持相减：vector、deque、string、普通数组都可以。list、set、map 的迭代器只能一个一个往前走，不能相减，这类容器上写 it - v.begin() 会编译失败。

// 片段：不同容器上"算位置"的能力不同
vector<int> v = {8, 3, 5};
auto it = find(v.begin(), v.end(), 5);
cout << (it - v.begin()) << '\n';        // 可以用：vector 的迭代器支持相减

list<int> lst = {8, 3, 5};
auto lit = find(lst.begin(), lst.end(), 5);
// cout << (lit - lst.begin()) << '\n';  // 不能这么写：list 的迭代器不支持相减

在只能逐个前进的容器上想数位置，可以自己数，或者用 distance(first, last)（选读）：它返回从 first 走到 last 需要多少步，list 上也能用，代价是逐个走过去。

find 是线性查找，数据不需要有序。 它最多比较 n 次，找不到时也要把整个区间走完。如果数据已经有序，用二分查找的 family（binary_search、lower_bound、upper_bound）会快得多；但那些函数要求区间已经按同一规则排好序，而这个前提 find 不需要。

find 不修改数据。 它只读取元素来比较，不会交换、删除或改变任何元素。要修改找到的元素，得自己通过返回的位置去改，比如 *it = 100;。

操作速查表

动手检查

第 1 题：预测输出

下面是一段片段（省略了头文件和 main），请先手推出输出，再运行核对：

vector<int> v = {8, 3, 5, 3};

auto it = find(v.begin(), v.end(), 5);
auto miss = find(v.begin(), v.end(), 7);

cout << (it - v.begin()) << ' ' << (miss == v.end()) << '\n';

第 2 题：修改代码

把下面这段“查找指定值”的程序改成用 find_if 查找第一个偶数，数据改成 {7, 3, 5, 4, 6}：

vector<int> v = {7, 3, 5, 4, 6};

auto it = find(v.begin(), v.end(), 4);     // 改成查找第一个偶数，条件自己写
if (it != v.end()) {
    cout << "第一个偶数：" << *it << "（下标 " << (it - v.begin()) << "）" << '\n';
} else {
    cout << "没有偶数" << '\n';
}

验证条件：先说出答案的元素和它前面有几个元素，再运行核对。

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

int main() {
    vector<int> v = {8, 3, 5, 3};

    auto it = find(v.begin(), v.end(), 5);
    auto miss = find(v.begin(), v.end(), 7);

    cout << (it - v.begin()) << ' ' << (miss == v.end()) << '\n';
    return 0;
}

2 1

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

bool isEven(int x) {
    return x % 2 == 0;
}

int main() {
    vector<int> v = {7, 3, 5, 4, 6};

    auto it = find_if(v.begin(), v.end(), isEven);
    if (it != v.end()) {
        cout << "第一个偶数：" << *it << "（下标 " << (it - v.begin()) << "）" << '\n';
    } else {
        cout << "没有偶数" << '\n';
    }
    return 0;
}

第一个偶数：4（下标 3）

立即练习

这道题用数组、循环和本页的查找写法可以先拿到大部分分。做完后请说明：你判断“找到了”用的是哪一句？如果把 find 换到已经排好序的数据上，还能更快吗？需要换成哪个函数？