搜索
Coddy C++ 标准模板库 课程的第 20 课，共 23 课。
搜索是指在一系列元素中定位某个元素位置的过程。
搜索算法是一种算法，它接收参数 x，并尝试在给定的值集合中查找值为 x 的元素。因此，如果不存在值为该值的元素，搜索可能会失败。
搜索技术和方法有很多种，但在 C++ 中，你将学习：
- 线性搜索
- 二分搜索
线性搜索
线性搜索是最基础的搜索技术，也很容易在 C++ 中实现。顾名思义，在线性搜索中，要搜索的键会与数据序列中的每个元素依次进行比较，直到找到它或序列结束。
Linear Search(sequence, key)
for each item in sequence:
if item == key
return item's index在实际代码中，线性搜索大致如下所示：
int linear_search(int array[], int n, int x)
{
for(int i = 0; i < n; i++)
if(array[i] == x)
return i;
return 0;
}
int main()
{
int array[] = {1, 2, 3, 4, 5};
int n = 5;
int x = 3;
cout << "The index of the element " << x << " is " << linear_search(array, n, x);Output:
The index of the element 3 is 2从上面的代码可以看出，线性搜索函数会遍历元素序列，直到找到匹配项。如果没有找到匹配项，它会返回 -1。
二分搜索
二分搜索是一种用于查找元素位置的搜索算法，但数组必须经过排序。
二分搜索算法使用“分而治之”的方法来搜索键。元素列表会不断地被分成两半，然后在更有可能包含目标元素的一半中继续搜索。
假设我们要搜索元素 x = 4
二分搜索的代码如下所示。
int binarySearch(int array[], int x, int left, int right) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (array[mid] == x)
return mid;
if (array[mid] < x)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
int main()
{
int array[] = {1, 5, 8, 10, 20};
int x = 10;
int n = 5;
int result = binarySearch(array, x, 0, n - 1);
if(result == -1)
cout << "Not found.";
else
cout << "The element is found at " << result;Output:
The element is found at 3记住什么是搜索、它的目的是什么，以及我们用它来做什么。记住如何实现线性搜索和二分搜索。通过练习，继续练习 C++ 中的高级技术。
挑战
中等输入中给出了 10 个数字。下一行有一个数字 N。第三行有 N 个数字，表示你需要输出到屏幕上的元素位置。
输入
10 20 30 40 50 60 70 80 90 100
3
20
50
80
输出
1 4 7
亲手试试
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
// Enter your code here
int main()
{
// Enter your code here
return 0;
}C++ 标准模板库中的所有课
自己练习： C++ 在线编译器