11.20顺序表查找,质数查找,折半查找,任意折查找

概念 

 

顺序表查找 

int search(int *a,int n, int key){
int i;
a[0]=key;
i=n;
while(a[i]!=key){
i--;}
return i;}

 就是从数组a的尾部开始找,a是从1开始计数的,所以找到0时,就说明查找失败。

顺序表找最大值

mv=a[1];
for(int i=2;i<=n;i++){
    if(mv<a[i]){
        mv=a[i]
    }
}

比较次数n-1 ,无论如何,都要比较n-1

同时找最大最小值

朴素查找

maxv=a[1];
minv=a[1];
for(int i=2;i<=n;i++){
    if(maxv<a[i]){
        maxv=a[i];
    }else if(minv > a[i]){
        minv=a[i];
    }
}

每次都先和最大值比,再和最小值比,如果比最大值大,那就一定不是最小值,就不需要再和最小值去比较 

最好情况为n-1,即升序,每次都是新的最大值,那么每次不需要和最小值比较,每次只和最大值比较即可

最坏情况为2(n-1),即降序 ,每次先和最大值比较,都不比最大值大,那么每次都需要和最小值比,即每个元素都要比两次

 快速查找

就是每次取两个,先让取的两个元素比较,就可以比较出一个大的和小的,这时就让大的和此时最大比,小的和最小的比,这样,每两个元素就只需要3次比较次数(一次元素自己比较,两次和最值比较)

相比朴素,朴素每两个要比较四次,每个元素都要和最大最小进行比较,快速就省了一次比较

若每次取三个,就起不到节省的次数,因为此时3个比较,就相当于3个里找最大值最小值,和每个元素直接比较,更加复杂

maxv=a[1],minv=a[1];
k=(n%2)+1;//n为奇数时,k从2开始;n为奇数时,k从1开始
while(k<n){//因为每次循环内都是k和k的下一位,所以k终止条件为n-1,不应该和n取等
    if(a[k]<a[k+1]){
        if(min>a[k]){
            minv=a[k];
        }
        if(maxv<a[k+1]){
            maxv=a[k+1];
        }
    }
    else{
         if(min>a[k+1]){
            minv=a[k+1];
        }
        if(maxv<a[k]){
            maxv=a[k];
        }
    }
    k+=2;
}

令k=(n%2)+1,n为奇数,如3时,那么从2开始,每次取两个,第一次就能取完,即2,3;如5时,2,3;4,5;

N为偶数,如2时,从1开始,每次取两个,第一次即取1,2 ;如4时,1,2;3,4;

查找区间质数

埃氏筛法

for(int k=2;k<=n;k++){
isp[k]=1;//先假定都是质数
}
for(int k=2;k<=n;k++){//从头开始遍历,2,3一定是质数
    if(isp[k]=1){//从底层开始,那么没有被标记过的一定是质数
        m=2*k;//基于找到质数基础上,在后续的序列中,把这个质数的所有倍数都删掉
        while(m<=n){//一直到越界
            isp[m]=0;//标记为不是质数
            m+=k;//每次都增加这个质数的一倍
        }
    }
}

不是质数的数,都可以被质数唯一表示 ,即每个数,都可以被质数表示

 

合数限定法 

while(!q.empty()){
    m=q.front();
    while(m*pk<=n){
        isp[m*pk]=0;
        enqueue(M,m);
        m=m*pk;
    }
}

欧拉筛法

 

每个数都可以被质数唯一表示,那么每个数一定存在构成其的最小质数,

那么在第一次遍历到那个最小质数时,就一定可以删除掉这个数 

相比埃氏筛法,

欧拉筛法中,如果当前数的质数,那么删掉已记录的所有已知质数,直到自己

如果不是质数,那么一直删到自己的最小质因数,比如4,只要2即可;9时,乘2要删一次,乘3要删一次,之后就停止了

也就是说,对于每个数,都是一直删,直到乘数是它的最小质因数

质数的最小质因数是其自身。

折半查找

int bs(s l,int key){
    int low=0,high=l.lengh-1,mind;
    while(low<=high){
        mid=(low+high)/2;
        if(l.data[mid]==key){
            return mid;
    }else if(l.data[mid]>key){
    high=mid-1;}else{
    low=mid+1;}
    }
return -1;}

查找终止的条件是左区间大于右区间

插值查找 

中间值可以表述为

左边意思是区间的中点;右边意思是,左端点加上区间长度的一半;

可改为

mid=low+(key-l.data[low])/(l.data[high]-l.data[low])*(high-low);

这个key就是要查找的值,low是此时区间里最小的值 

斐波那契查找

int search(int *a,int n, int key){
    int low,high,mid,i,k;
    low=0,high=n,k=0;

 

 

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/170069.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

基于 Python中的深度学习:神经网络与卷积神经网络

当下&#xff0c;深度学习已经成为人工智能研究和应用领域的关键技术之一。作为一个开源的高级编程语言&#xff0c;Python提供了丰富的工具和库&#xff0c;为深度学习的研究和开发提供了便利。本文将深入探究Python中的深度学习&#xff0c;重点聚焦于神经网络与卷积神经网络…

实现领域驱动设计-应用结构

写在前面&#xff1a; DDD的一大好处便是它并不需要使用特定的架构。我们可以在整个系统中使用多种风格的架构。有些架构包围着领域模型&#xff0c;能够全局性地影响系统&#xff0c;而有些架构则满足了某些特定的需求。我们的目标是选择适合于自己的架构和架构模式。 在选择架…

Java格式化类Format

文章目录 Format介绍Format方法- format&#xff08;格式化&#xff09;- parseObject&#xff08;解析&#xff09; 格式化分类日期时间格式化1. DateFormat常用方法getInstancegetDateInstancegetTimeInstancegetDateTimeInstance 方法入参styleLocale 2. SimpleDateFormat常…

【HarmonyOS】鸿蒙应用开发基础认证题目

系列文章目录 【HarmonyOS】鸿蒙应用开发基础认证题目&#xff1b; 文章目录 系列文章目录前言一、判断题二、单选题三、多选题总结 前言 随着鸿蒙系统的不断发展&#xff0c;前不久&#xff0c;华为宣布了重磅消息&#xff0c;HarmonyOS next 开发者版本会在明年&#xff08;…

编写函数实现简单的插值进入有序数组问题

归纳编程学习的感悟&#xff0c; 记录奋斗路上的点滴&#xff0c; 希望能帮到一样刻苦的你&#xff01; 如有不足欢迎指正&#xff01; 共同学习交流&#xff01; &#x1f30e;欢迎各位→点赞 &#x1f44d; 收藏⭐ 留言​&#x1f4dd; 老骥伏枥&#xff0c;志在千里&…

JVS低代码表单设计:数据联动详解(多级数据级、数据回显等)

在这信息化时代&#xff0c;表单作为数据的收集和展示工具&#xff0c;已经渗透到不同的角落。JVS低代码对表单的设计和操作进行了不断的优化和创新。其中&#xff0c;联动回显作为一项重要的功能&#xff0c;无论是多级数据级联控制、组件的联动控制&#xff0c;还是多表的数据…

Unexpected WSL error

问题描述 启动 Docker Desktop 报错 Unexpected WSL error&#xff0c;报错完整信息如下&#xff1a; Docker Desktop - Unexpected WSL error An unexpected error was encountered while executing a WSL command, Commoncauses include access rights issues, which occur…

[github初学者教程] 分支管理-以及问题解决

作者&#xff1a;20岁爱吃必胜客&#xff08;坤制作人&#xff09;&#xff0c;近十年开发经验, 跨域学习者&#xff0c;目前于新西兰奥克兰大学攻读IT硕士学位。荣誉&#xff1a;阿里云博客专家认证、腾讯开发者社区优质创作者&#xff0c;在CTF省赛校赛多次取得好成绩。跨领域…

虚拟化逻辑架构: 创建KVM中的VM与实现VNC远程登录

目录 一、实验 1.安装KVM环境管理工具并创建VM&#xff08;虚拟机&#xff09; 2.Windows使用VNC Viewer连接KVM中的VM&#xff08;虚拟机&#xff09; 二、问题 1.如何下载安装VNC Viewer 一、实验 1.安装KVM环境管理工具并创建VM&#xff08;虚拟机&#xff09; (1) 采…

golang学习笔记——日志记录

文章目录 日志与错误log包记录到文件记录框架Contextual LoggingLeveled LoggingSetting Global Log Level Error Logging 日志与错误 通常&#xff0c;发生错误时&#xff0c;最终用户只会看到一条消息&#xff0c;指示程序出现问题。日志是简单错误消息以外的更多信息。 lo…

城市智慧路灯智能照明管理系统简介

城市路灯存在着开关灯控制方式单、亮灯时间不准确、巡查困难、故障处理不及时、亮灯率无法把控等问题&#xff0c;从而导致路灯系统能耗高&#xff0c;维护成本高。传统的路灯控制系统已无法满足智慧城市管理的需要&#xff0c;智能路灯照明控制系统从而得到广泛应用。 叁仟智…

【C++】使用std::vector()函数实现矩阵的加、减、点乘、点除等运算

本文通过vector&#xff08;&#xff09;函数表示矩阵的形式&#xff0c;对 加、减、点乘、点除等运算进行编码和运行&#xff0c;相应结果如下文所述。 #include <iostream> #include <vector>using namespace std;// 矩阵加法 vector<vector<int>> …

buildadmin+tp8表格操作(4) Table组件,baTable类和 elementplus中的属性关系

在buildadmin 中&#xff0c;table组件是封装的 element-plus中的方法&#xff0c; 所以说&#xff0c; 在 buildadmin的table组件中&#xff0c;是可以通用 elementplus中的属性的 以上这些属性&#xff0c; 在buildadmin中都是可以使用的 使用方式和 elementplus el-table用…

linux rsyslog综合实战1

本次我们通过rsyslog服务将A节点服务器上的单个日志(Path:/var/log/245-1.log)实时同步到B节点服务器目录下(Path:/opt/rsyslog/245) 1.rsyslog架构 2.环境信息 环境信息 HostnameIpAddressOS versionModuleNotersyslog1192.168.10.245CentOS Linux release 7.9.2009 (Core)rs…

工作记录---为什么双11当天不能申请退款?(有趣~)

为什么&#xff1f; 服务降级了 服务降级&#xff1a; 当服务器压力剧增的情况下&#xff0c;根据实际业务情况及流量&#xff0c;对一些服务和页面有策略的不处理或换种简单的方式处理&#xff0c;从而释放服务器资源以保证核心交易正常运作或高效运作。 分布式系统的降级…

十四、Docker的基本操作

目录 &#xff08;一&#xff09;镜像命令 一、拉取Nginx 二、查看镜像 三、导出文件 四、删除镜像 五、加载镜像 &#xff08;二&#xff09;容器命令 一、例子&#xff1a;运行一个nginx容器 1、输入运行命令 2、使用命令查看宿主机ip 3、在外部浏览器访问 4、查看…

crmchat安装搭建教程文档 bug问题调试

一、安装PHP插件&#xff1a;fileinfo、redis、swoole4。 二、删除PHP对应版本中的 proc_open禁用函数。 一、设置网站运行目录public&#xff0c; 二、设置PHP版本选择纯静态。 三、可选项如有需求则开启SSL,配置SSL证书&#xff0c;开启强制https域名。 四、添加反向代理。 …

苹果CMS首涂第30套可装修DIY主题模板免授权版

这是一款可以装修的主题&#xff0c;类似淘宝店装修一样&#xff0c;可以针对首页、栏目页、详情页、播放页进行自定义装修&#xff0c;内置10个模块自由选择、添加、修改、删除、排序操作&#xff0c;后续升级还会增加更多实用和个性模块供选择&#xff0c;主题内包含的导航、…

类与对象(上篇)

前言 在之前我们学的C入门主要是为现在学习类与对象打基础&#xff0c;今天我们才算真正开始学习C了。因为类与对象的知识点比较多&#xff0c;所以我们将它分为三部分讲解&#xff0c;今天我们学习类与对象的上篇。 一、面向过程和面向对象的初步认识 1、面向过程 面向过程顾…

基于安卓android微信小程序的个人管理小程序

运行环境 开发语言&#xff1a;Java 框架&#xff1a;ssm JDK版本&#xff1a;JDK1.8 服务器&#xff1a;tomcat7 数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09; 数据库工具&#xff1a;Navicat11 开发软件&#xff1a;eclipse/myeclipse/idea Maven包&a…