寻找指定元素

2023-12-23 18:37:33

寻找指定元素

题目链接

题意

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

思路

  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 函数中调用以执行查找操作。

文章来源:https://blog.csdn.net/pandawen123/article/details/135171583
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。