【查找算法】解析学习四大常用的计算机查找算法 | C++

本文涉及的产品
全局流量管理 GTM,标准版 1个月
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
云解析 DNS,旗舰版 1个月
简介: 在数据处理的过程中,能否在最短时间内去找到目的数据,是编程开发人员非常值得关心的一个问题。所谓查找,也被称为搜索,它是指从数据文件中找出满足某些条件的记录。在数据结构中描述算法时习惯用“查找”,而在搜索引擎中找信息或资料时习惯用“搜索”。我们在电话簿中查找某人的电话号码,电话簿就像是数据文件库,而姓名就是去查找电话号码的键值。我们经常使用的搜索引擎所设计的Spider程序(网页抓取程序爬虫)会主动经由网站上的超链接“爬行”到另一个网站,搜集每个网站上的信息并且收录到数据库中,这其中就涉及到了今天要讲的查找算法。

前言

       在数据处理的过程中,能否在最短时间内去找到目的数据,是编程开发人员非常值得关心的一个问题。所谓查找,也被称为搜索,它是指从数据文件中找出满足某些条件的记录。在数据结构中描述算法时习惯用“查找”,而在搜索引擎中找信息或资料时习惯用“搜索”。我们在电话簿中查找某人的电话号码,电话簿就像是数据文件库,而姓名就是去查找电话号码的键值。我们经常使用的搜索引擎所设计的Spider程序(网页抓取程序爬虫)会主动经由网站上的超链接“爬行”到另一个网站,搜集每个网站上的信息并且收录到数据库中,这其中就涉及到了今天要讲的查找算法。

查找算法

       在查找算法中,比较常见的有顺序法、二分法、插入法和斐波那契法等。查找的操作和算法有关,具体的操作方式和进行方式与所选择的数据结构有关。计算机查找数据的优点就是快速,但是对于不同程度下的数据量,查找可以分为内部查找(数据量较小的文件)和外部查找(数据量较大的文件)。影响查找时间长短的主要因素有算法,数据存储的方式以及结构。查找可以分为静态查找和动态查找。静态查找是指数据元素在查找的过程中不会有添加,删除,更新等操作。动态查找是指所查找的数据在查找过程中会经常地添加,删除或更新。

一、顺序查找

1.什么是顺序查找法?

(1)简要介绍

       顺序查找法是一种比较简单的查找法。该算法就是利用了计算机便于处理大量数据的这一特点,从而来进行实现的。该方法的优点就是文件在查找前不需要进行任何处理与排序;而缺点是查找的速度比较慢,因为无论数据顺序是什么情况,它都需要从头到尾都去遍历一遍。如果数据元素没有重复,那么找到数据元素就可以中止查找。说明最差的情况是n次查找,最好的情况下是1次查找。

(2)具体情况

       在8个数据元素中,去顺序查找元素89。情况如下图所示:

对于大量重复的数据元素来说,顺序查找法一般是不会使用的,因为它的时间效率极低并且可能会因为元素中的重复项而造成错误。但是对于少量的数据元素来说,这无疑是一种非常快又准确性高的简单方法。

(3)算法分析

       ①时间复杂度:如果数据没有重复且找到数据就可以中止,那么在最差情况下就是未找到数据,进行了n次比较,所以时间复杂度为O(n)。

       ②当数据量很大时,不适合使用顺序查找法。如果事先预估到所查找的数据在文件前面的部分,就可以减少查找的时间。

       ③在平均情况下,假设数据出现的概率相等,则需要进行(n+1)/2次比较。

2.案例实现

(1)范例情况:用随机法生成80个1~100的整数,用顺序查找法去查找我们指定元素是否存在,如果存在说明其所在的位置。

(2)代码展示:

#include<iostream>
#include<cstdlib>
using namespace std;
class order {
public:
  int data[80];
  int val = 0;
  //构造函数 随机给data中分配数据
  order() {
  for (int i = 0; i < 80; i++)
    data[i] = (rand() % 100) + 1;
  }
  void order_start() {
  cout << "请输入要猜测的数:";
  cin >> val;
  for (int i = 0; i < 80; i++)
  {
    if (data[i] == val) {
    cout << "该数" << data[i] << "存在 所在位置为" << i + 1 << endl;
    val = 0;
    }
  }
  if (val != 0)
    cout << "该数不存在" << endl;
  }
  //析构函数 展现所有元素
  ~order() {
  cout << "所有随机数据元素如下:" << endl;
  for (int i = 0; i < 80; i++) 
    cout << data[i] << "[" << i << "]" << " ";
  }
};
int main()
{
  order o;
  while (o.val != -1)
  {
  o.order_start();
  }
}

二、二分查找法

1.什么是二分查找法?

(1)简要介绍

       如果一组数据已经事先排好了顺序,那么就可以用二分查找法来进行查找。二分查找法的基本方法就是将数据分成两等份,比较目标寻找值与中间值的大小。如果小于中间值,那么我们就可以确定要寻找的数据在前半部分,否则在后半部分。重复上述步骤将其分割直到找到或确定不存在为止。

(2)具体情况

       用二分查找法对已经完成排序的一组数列,查找其元素101所在的位置。具体情况如下图所示:

(3)算法分析

       ①时间复杂度:因为每次的查找都会比上一次查找少一半的范围,所以最多只需比较(log2^n)+1或(log2^(n+1))次,时间复杂度O(log2^n)。

       ②二分查找法必须是经过排序的数列,且数据元素都要加载到内存中才能进行查找。

       ③二分查找法适用于不需要增删的静态数据。

2.案例实现

(1)范例程序:用二分查找法查找10个1~10随机数据中指定数据元素的位置,并且输出随机产生的这10个数据。

(2)代码展示:

#include<iostream>
using namespace std;
#define size 10
class dichotomy {
public:
  int data[size];
  int val = 0;
  dichotomy() {
  for (int i = 0; i < size; i++)
    data[i] = (rand() % 10) + 1;
  }
  void sort() {
  for (int i = 0; i < size-1; i++) {
    for (int j = i+1; j < size; j++) {
    if (data[i] > data[j])
    {
      int temp;
      temp = data[i];
      data[i] = data[j];
      data[j] = temp;
    }
    }
  }
  }
  void dichotomy_start(int len_left,int len_right){ 
  int record=0;
  while (len_left <= len_right )
  {
    int mid = (len_right + len_left) / 2;
    if (val < data[mid]) {
    cout << "目标数在中间值的左边" << endl;
    len_right = mid - 1;
    }
    else if (val > data[mid]) {
    cout << "目标数在中间值的右边" << endl;
    len_left = mid + 1;
    }
    else if(val==data[mid]){
    cout << "在第" << mid + 1 << "个位置处找到了" << "该元素" << data[mid] << endl;
    val = 1;
    break;
    } 
  } 
  if (val != 1) {
    cout << "随机产生的这几个数中不存在要猜测的这个数值" << endl;
  }
  }
  ~dichotomy() {
  cout << "所有随机数据元素如下:" << endl;
  for (int i = 0; i < size; i++) 
    cout << data[i] << "[" << i << "]" << " ";
  }
};
int main()
{
  dichotomy d;
  d.sort();
  while (d.val!=-1)
  {
  cout << "请输入要猜测的数:";
  cin >> d.val;
  if (d.val != -1)
    d.dichotomy_start(0, size - 1);
  else
    break;
  }
}

(3)结果展示:


三、插值查找法

1.什么是插值查找法?

(1)简要介绍

       插值查找法又被称为插补查找法,是对二分查找的进一步改进。它是按照数据位置的分布,利用公式去预测数据所在的位置,再用二分法的方式渐渐逼近。该查找法的公式如下:



其中,key是要去查找的键值,data[high],data[low]是剩余待查找记录中的最大值和最小值。特别注意:使用该查找算法之前需要对要排序的数据进行排序。


(2)具体情况

假设数据项为n,其插值查找法的步骤如下:

       ①讲记录从小到大的顺序给予1,2,...,n的编号;

       ②令low=1,high=n;

       ③当low

       ④令Mid=low+((key-data[low])/(data[high]-data[low]))*(high-low);

       ⑤若key

       ⑥若key>key[mid]且low≠Mid+1,则令low=Mid+1;

       ⑦若key=key[mid],则表示成功找到了键值的位置;


(3)算法分析

       ①插值查找法优于顺序查找法,如果数据的分布越平均,查找速度就越快,甚至可能第一次就找到数据。插值查找法的时间复杂度取决于数据的分布情况,平均而言优于O(log2^n)。

2.案例实现

①范例程序:用插值查找法去查找10个随机数据中,指定元素数据所在的位置。

②代码展示:

#include<iostream>
using namespace std;
class interpolation_search {
public:
  int data[10];
  int val = 0;
  interpolation_search() {
  for (int i = 0; i < 10; i++)
    data[i] = (rand() % 10) + 1;
  }
  void sort() {
  for (int i = 0; i < 10-1; i++)
  {
    for (int j = i + 1; j < 10; j++)
    {
    if (data[i] > data[j])
    {
      int temp;
      temp = data[i];
      data[i] = data[j];
      data[j] = temp;
    }
    }
  }
  }
  void interpolation_search_start() {
  int low = 0, high = 9;
  while (low<=high)
  {
    int mid = low + ((val - data[low]) / (data[high] - data[low])) * (high - low);
    if (val < data[mid]) {
    cout << "目标元素在mid的左边" << endl;
    high = mid - 1;
    }
    if (val > data[mid]) {
    cout << "目标元素在mid的右边" << endl;
    low = mid + 1;
    }
    if (val == data[mid]) {
    cout << "找到了该元素,该元素位置在" << mid + 1 << "处" << endl;
    val = 1;
    break;
    }
  }
  if (val != 1) {
    cout << "随机生成的数据中没有你要去查找的数据" << endl;
  }
  }
  ~interpolation_search() {
  cout << "随机产生的数据元素如下" << endl;
  for (int i = 0; i < 10; i++)
    cout << data[i] << " ";
  }
};
void text()
{
  interpolation_search is;
  is.sort();
  while (is.val != -1)
  {
  cout << "请输入你要查找的数:";
  cin >> is.val;
  is.interpolation_search_start();
  }
}
int main()
{
  text();
}

③结果展示:

四、斐波那契查找法

1.什么是斐波那契查找法?

(1)简要介绍

       斐波那契查找法又被称为斐氏查找法,该方法与二分法一样都是以分割范围来进行查找的,不同的是该方法不是以对半的方式来进行分割的,而是利用斐波那契级数(0、1、1、2、3、5、8、13、21、34、55、...)来进行分割的。该查找法的优点就是只需要用到加减运算,这从计算机运算的底层来看效率是相对较高的。并且该查找法会用到斐波那契树,所以我们应该先来了解该树的基本情况和特点。

(2)具体情况

斐波那契树的建立原则:

       ①斐波那契树的左右子树都是斐波那契树。

       ②斐波那契树的树根一定是一个斐波那契数,且子节点与父节点之间的差值的绝对值仍为斐波那契数。

       ③当k≥2时,斐波那契树的树根为Fib(k),左子树为(k-1)层斐波那契树,右子树为(k-2)层斐波那契树。

       ④当数据个数n确定时,若想确定斐波那契树的层数k为多少,必须找到一个最小的k值,使斐波那契层数的Fib(k+1)≥n+1。



也就是说当数据个数为n,我们找到一个最小的斐波那契数Fib(k+1)使得Fib(k+1)>n+1时,Fib(k)就是这棵树的树根,而Fib(k-2)就是与左右子树开始的差值,左子树去减,右子树去加。例如去求取n=33的斐波那契树。由于n=33,则n+1=34为一棵斐波那契树。由斐波那契公式可得知Fib(0)=0,Fib(1)=1,Fib(2)=1,Fib(3)=2,Fib(4)=3,Fib(5)=5,Fib(6)=8,Fib(7)=13,Fib(8)=21,Fib(9)=34。可知Fib(k+1)≥n+1为Fib(8+1)=34,k=8所以建立二叉树的树根为Fib(8)=21。左子树的树根为Fib(8-1)=13;右子树的树根为Fib(8)+Fib(8-2)=21+8=29;从而依照上述步骤建立的斐波那契树如下图所示:



若我们要查找的键值为key,首先要去比较数组下标Fib(k)和键值key,此时就将会出现多种情况如下:

       ①key值较小,落在了1~Fib(k)-1位置上,所以继续去查找1~Fib(k)-1的数据;key值较大,落在了Fib(k)+1~Fib(k+1)-1的位置上,所以继续去查找Fib(k)+1~Fib(k+1)-1的数据。

       ②当键值与数组下标Fib(k)的值相等时,则表示成功的查找到了目标数据元素的位置。

(3)算法分析

      ① 斐波那契查找法虽然平均比较次数少于二分查找法,但在最坏的情况下还是二分查找法较快,并且斐波那契查找法相对复杂,因为它需要去额外产生一棵斐波那契树。

2.案例实现

①范例程序:用斐波那契树查找法去查找指定键值是否存在,并且如果存在其在哪个具体的位置。

②代码展示:

#include<iostream>
using namespace std;
#define size 10
class Fib {
public:
  int data[size];
  int val = 0;
  Fib() {
  for (int i = 0; i < size; i++)
    data[i] = (rand() % 10) + 1;
  }
  int Fib_start(int n) {
  if (n == 0 || n == 1)
    return 1;
  else
    return Fib_start(n - 1) + Fib_start(n - 2);
  }
  int Fib_search_start() {
  int index = 2;
  while (Fib_start(index) <= size)
    index++;
  index--;
  int rootnode = Fib_start(index);
  int diff_1 = Fib_start(index - 1);
  int diff_2 = rootnode - diff_1;
  rootnode--;
  while (1)
  {
    if (val == data[rootnode])
    {
    return rootnode;
    }
    else
    {
    if (index == 2)
      return size;
    if (val < data[rootnode])
    {
      rootnode = rootnode - diff_2;
      int temp = diff_1;
      diff_1 = diff_2;
      diff_2 = temp - diff_2;
      index = index - 1;
    }
    else
    {
      if (index == 3)
      return size;
      rootnode = rootnode + diff_2;
      diff_1 = diff_1 - diff_2;
      diff_2 = diff_2 - diff_1;
      index = index - 2;
    }
    }
  }
  }
  ~Fib()
  {
  cout << "随机生成的所有数据情况如下" << endl;
  for (int i = 0; i < 10; i++)
    cout << data[i] << " ";
  }
};
void text()
{
  Fib f;
  while (f.val != -1)
  {
  cout << "请输入要查找的值:";
  cin >> f.val;
  int count = f.Fib_search_start();
  if(count==size)
    cout << "没有找到该数据元素" << endl;
  else
    cout << "在第" << count + 1 << "个位置找到了该数据元素" << f.val << endl;
  }
}
int main()
{
  text();
}

③结果展示:

总结

       以上就是我们对四类查找算法的分析与学习,查找算法在程序设计问题中经常作为一种重要中间的步骤。比如查找数据后,再对数据进行指定步骤的操作行为,所以要在不同的算法题型中合理地运用查找算法,从而达到最高的效率来解决相应的问题。



目录
相关文章
|
2月前
|
存储 算法 Java
解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用
在Java中,Set接口以其独特的“无重复”特性脱颖而出。本文通过解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用。
54 3
|
3天前
|
算法 网络安全 区块链
2023/11/10学习记录-C/C++对称分组加密DES
本文介绍了对称分组加密的常见算法(如DES、3DES、AES和国密SM4)及其应用场景,包括文件和视频加密、比特币私钥加密、消息和配置项加密及SSL通信加密。文章还详细展示了如何使用异或实现一个简易的对称加密算法,并通过示例代码演示了DES算法在ECB和CBC模式下的加密和解密过程,以及如何封装DES实现CBC和ECB的PKCS7Padding分块填充。
16 4
2023/11/10学习记录-C/C++对称分组加密DES
|
14天前
|
机器学习/深度学习 人工智能 算法
深入解析图神经网络:Graph Transformer的算法基础与工程实践
Graph Transformer是一种结合了Transformer自注意力机制与图神经网络(GNNs)特点的神经网络模型,专为处理图结构数据而设计。它通过改进的数据表示方法、自注意力机制、拉普拉斯位置编码、消息传递与聚合机制等核心技术,实现了对图中节点间关系信息的高效处理及长程依赖关系的捕捉,显著提升了图相关任务的性能。本文详细解析了Graph Transformer的技术原理、实现细节及应用场景,并通过图书推荐系统的实例,展示了其在实际问题解决中的强大能力。
98 30
|
18天前
|
存储 算法
深入解析PID控制算法:从理论到实践的完整指南
前言 大家好,今天我们介绍一下经典控制理论中的PID控制算法,并着重讲解该算法的编码实现,为实现后续的倒立摆样例内容做准备。 众所周知,掌握了 PID ,就相当于进入了控制工程的大门,也能为更高阶的控制理论学习打下基础。 在很多的自动化控制领域。都会遇到PID控制算法,这种算法具有很好的控制模式,可以让系统具有很好的鲁棒性。 基本介绍 PID 深入理解 (1)闭环控制系统:讲解 PID 之前,我们先解释什么是闭环控制系统。简单说就是一个有输入有输出的系统,输入能影响输出。一般情况下,人们也称输出为反馈,因此也叫闭环反馈控制系统。比如恒温水池,输入就是加热功率,输出就是水温度;比如冷库,
127 15
|
2月前
|
搜索推荐 算法
插入排序算法的平均时间复杂度解析
【10月更文挑战第12天】 插入排序是一种简单直观的排序算法,通过不断将未排序元素插入到已排序部分的合适位置来完成排序。其平均时间复杂度为$O(n^2)$,适用于小规模或部分有序的数据。尽管效率不高,但在特定场景下仍具优势。
|
1月前
|
自然语言处理 编译器 Linux
|
25天前
|
设计模式 安全 数据库连接
【C++11】包装器:深入解析与实现技巧
本文深入探讨了C++中包装器的定义、实现方式及其应用。包装器通过封装底层细节,提供更简洁、易用的接口,常用于资源管理、接口封装和类型安全。文章详细介绍了使用RAII、智能指针、模板等技术实现包装器的方法,并通过多个案例分析展示了其在实际开发中的应用。最后,讨论了性能优化策略,帮助开发者编写高效、可靠的C++代码。
35 2
|
3天前
|
安全 编译器 C++
C++ `noexcept` 关键字的深入解析
`noexcept` 关键字在 C++ 中用于指示函数不会抛出异常,有助于编译器优化和提高程序的可靠性。它可以减少代码大小、提高执行效率,并增强程序的稳定性和可预测性。`noexcept` 还可以影响函数重载和模板特化的决策。使用时需谨慎,确保函数确实不会抛出异常,否则可能导致程序崩溃。通过合理使用 `noexcept`,开发者可以编写出更高效、更可靠的 C++ 代码。
10 0
|
3天前
|
存储 程序员 C++
深入解析C++中的函数指针与`typedef`的妙用
本文深入解析了C++中的函数指针及其与`typedef`的结合使用。通过图示和代码示例,详细介绍了函数指针的基本概念、声明和使用方法,并展示了如何利用`typedef`简化复杂的函数指针声明,提升代码的可读性和可维护性。
20 0
|
1月前
|
算法 Linux 定位技术
Linux内核中的进程调度算法解析####
【10月更文挑战第29天】 本文深入剖析了Linux操作系统的心脏——内核中至关重要的组成部分之一,即进程调度机制。不同于传统的摘要概述,我们将通过一段引人入胜的故事线来揭开进程调度算法的神秘面纱,展现其背后的精妙设计与复杂逻辑,让读者仿佛跟随一位虚拟的“进程侦探”,一步步探索Linux如何高效、公平地管理众多进程,确保系统资源的最优分配与利用。 ####
70 4

推荐镜像

更多