寻找指定元素

寻找指定元素

题目链接

题意

在一个已经排序的整数数组（序列）中查找一个特定的元素

思路

1. 输入数据：获取数组的大小 n 和要查找的特定元素 x，以及整个数组 a 的元素。
2. 二分查找：定义了一个 check() 函数，实现二分查找算法。它通过不断缩小查找范围来找到元素 x 的位置，如果找到则返回位置，否则返回 -1。
3. 输出结果：在 main() 函数中，调用 check() 函数并输出查找结果。如果找到了元素 x，则输出其在数组中的位置；如果没有找到，则输出 -1。

坑点

1. 数组排序
2. 边界条件

算法一：二分查找

时间复杂度

O(log n)

实现步骤

1. 初始化边界
2. 执行二分查找
3. 调整边界并返回结果

代码

#include<iostream>
using namespace std;
const int N = 1e6;
int n, a[N], x;
//定义了一个常量 N，表示数组的大小。然后定义了三个整型变量：n 用于存储数组的大小，a 是一个整数数组，x 是要查找的特定元素
int check() {//定义了一个 check 函数，实现了二分查找算法
    int l = 0, r = n - 1;//l 和 r 分别表示查找范围的左边界和右边界
    while (l <= r) {
        int mid = l + (r - l) / 2;//计算中点 mid 并比较 a[mid] 和 x 的值，来决定是否找到了目标元素。
        if (a[mid] == x) {
            return mid;//如果找到了，就返回元素的位置
        } else if (a[mid] < x) {
            l = mid + 1;//如果 a[mid] 小于 x，则将左边界 l 移动到 mid + 1
        } else if (a[mid] > x) {
            r = mid - 1;//如果 a[mid] 大于 x，则将右边界 r 移动到 mid - 1。
        }
    }
    return -1;
}
//如果循环结束后还没有找到元素，则返回 -1。
int main() {
    cin>>n>>x;//输入读取数组的大小 n 和要查找的元素 x
    for (int i = 0; i < n; i++) {//通过一个 for 循环读取数组 a 的所有元素
        cin>>a[i];
    }
    cout<<check();//调用 check 函数进行查找，并将结果输出到标准输出 cout
    return 0;
}
 //如果找到了元素，将输出元素的位置，并结束程序；如果没有找到，输出 -1。

总结

要求在一个已排序的数组中实现二分查找算法，查找并返回特定目标值的位置，若未找到则返回 -1。用 check 函数实现二分查找，之后在 main 函数中调用以执行查找操作。