数据结构与算法基础(王卓)(28)线性表的查找(2):顺序查找(二分查找、分块查找)

本文主要是介绍数据结构与算法基础(王卓)(28)线性表的查找(2):顺序查找(二分查找、分块查找),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

二、折半查找(二分或对分查找)

Project 1:

修正后的结果如下:

Project 2:

问题(1):【ST.R[mid].key】

问题(2):等于:(==)而非(=)

问题(3):关于除、除以、整除

一、关于除和除以的区别:

二、关于整除的问题:

问题(4):low等于high时我们应该怎么处理?

所以对于这个情况,我们还是把他放到while循环里面比较合适

Project 3:(最终结果)

PPT上写的标准答案版本(确实也有可取之处)

PPT上补充:递归实现版本

三、分块查找


二、折半查找(二分或对分查找)

前置条件和前面一样

最开始根据PPT示(实)例写出的程序框架:

一开始:

low:第一位

high:最后一位

mid:正中间

查找数小于mid:

把high移动到mid前面一位( - 1)

再取新mid = 新【正中间】

查找数大于mid:

把low移动到mid后面一位( + 1)

再取新mid = 新【正中间】

然而这里,我写的只是一些框架的核心规则,并没有梳理出程序具体是怎么运行的逻辑流程

所以写的和标准答案写的不一样:

Project 1:

int Seaarch_Bin(SSTable ST, KeyType key)
//binary:二进制的; 仅基于两个数字的; 二元的; 由两部分组成的;
{int low = 1, high = ST.length, mid = (low + high) / 2;while (key != mid){if (key < mid){high = mid - 1;mid = (low + high) / 2;}else if (key < mid)//else{low = mid + 1;mid = (low + high) / 2;}}if (low > high)return false;elsereturn mid;
}

里面除了梳理逻辑以外,还存在另外的诸多问题,当然:

写程序之前最好肯定还是梳理出程序具体是怎么运行的逻辑流程,这是肯定的

上面这一版本还存在着诸多的问题:

  • key在比较时不应该写【mid】应改成【ST.R[mid].key】(Project 2中我们会对此作出具体详细的剖析解释)
  • while循环当中无论是在哪种情况(分支),(都)始终执行【mid = (low + high) / 2;】语句,应当(可以)考虑合并语句在【if】语句之外

修正后的结果如下:

(我觉得修改成如下结果以后,这个结果写的也没有错,只不过我没有那么确定一定没错)

int Seaarch_Bin(SSTable ST, KeyType key)
//binary:二进制的; 仅基于两个数字的; 二元的; 由两部分组成的;
{int low = 1, high = ST.length, mid = (low + high) / 2;while (key != ST.R[mid].key){if (key < ST.R[mid].key)high = mid - 1;else if (key < ST.R[mid].key)//elselow = mid + 1;mid = (low + high) / 2;}if (low > high)return false;elsereturn mid;
}

除此之外,我们首当其冲要做的:就是要梳理出程序具体是怎么运行的逻辑流程

把程序转换为和PPT上类似的逻辑形式:(但是这并不代表我写的是错的)

Project 2:

int Seaarch_Bin(SSTable ST, KeyType key)
//binary:二进制的; 仅基于两个数字的; 二元的; 由两部分组成的;
{//不是从R开始吗???int low = 1, high = ST.length, mid = (low + high) / 2;while (low<=high)//一开始我们是想写(key != mid)的判断语句的,但是如果这样写的话我们最后就无法判断他有没有找到{if (key = mid)return mid;else if (key < mid){high = mid - 1;mid= (low + high) / 2;}else if (key > mid)//else{low = mid + 1;mid = (low + high) / 2;}}return 0;
}

问题(1):【ST.R[mid].key】

key在比较时不应该写【mid】应改成【ST.R[mid].key】

(Project 1中也有类似一样的问题)

具体解释:


首先,我们要意识到:

我们的key要对比的对象,是顺序表ST(数组)内部的具体某个位序(某一格)里面的具体数值

 这个时候我们再去看顺序表的构造,我们就会意识到:

事实上实际顺序表ST和我们原来想当然的写的程序的东西不一样

typedef int KeyType;

//数据元素类型定义

struct ElemType

{

    KeyType key;  //关键字域

    //...           //其他域

};

struct SSTable

    //Sequential Search Table

{

    ElemType* R;  //表基址

    int length;   //表长

}; 

SSTable ST;  //定义顺序表ST

实际上,我们前面写程序的效果是:

让【key】和【指针指向的元素位序序号】去比较

而我们实际需要实现的效果是:

让【key】和【指针指向的元素数据】去比较

而这个KeyType元素数据(关键字数据),则在:

表基址R(虽然我也不知道这个表基址是什么玩意)的关键字域key当中

加上数据类型:

在【(ElemType*)类型的】表基址R【(KeyType)类型的】关键字域key当中

所以,mid应改为:ST.R[mid].key


而这样的解释,实际上也顺带解决了我们在编写程序时:

数组地址顺序不是从R开始吗???

的问题


问题(2):等于:(==)而非(=)


问题(3):关于除、除以、整除

一、关于除和除以的区别:

6除以2:divided by

6÷2=3

6除2:divide

2÷6=⅓

2除6:divide

6÷2=3

2除以6:divided by

2÷6=⅓

二、关于整除的问题:

整除的取整:

取整数,舍去小数

注意:并非四舍五入

在计算机当中,关于除法,只有一个运算符号,那就是“/”

而关于其是否整除:

是表示整除的取整结果【注意:并非四舍五入】还是带小数的最终运算结果,取决于除数和被除数,更准确的说,是除法过程中,所有的运算量

若所有的运算量【所有的 除数和被除数】都为整型(int型):

结果取整,舍去小数(注意:不是四舍五入)

若所有的运算量【所有的 除数和被除数】中只要有一个运算量为实型(实数类型:float、double)

结果保留小数(保留小数位数格式向实数的类型看齐,能更精确就更精确)


问题(4):low等于high时我们应该怎么处理?

在前面的实例中,我们写了low和high大于和小于的情况

那么当low和high等于时我们应该怎么处理?

设计具体实例尝试,假设:

位序123
数据222324
指针lowmidhigh

 所以我们最终得到的结论就是说:

当low等于high时:

如果key不等于【low和high还有mid】,那么就查找失败

如果等于,输出指针

所以对于这个情况,我们还是把他放到while循环里面比较合适


Project 3:(最终结果)

int Seaarch_Bin(SSTable ST, KeyType key)
//binary:二进制的; 仅基于两个数字的; 二元的; 由两部分组成的;
{int low = 1, high = ST.length, mid = (low + high) / 2;while (low <= high){if (key == ST.R[mid].key)return mid;else if (key < ST.R[mid].key)high = mid - 1;else if (key > ST.R[mid].key)//elselow = mid + 1;mid = (low + high) / 2;}return 0;
}

附:

PPT上写的标准答案版本(确实也有可取之处)

他相当于在我们前面写的程序的基础上再简化一步:

一开始不必给mid赋值,只需要在每次循环的开始给mid进行赋值操作即可

int Seaarch_Bin(SSTable ST, KeyType key)
//binary:二进制的; 仅基于两个数字的; 二元的; 由两部分组成的;
{int low = 1, high = ST.length,mid; while (low <= high){mid = (low + high) / 2;if (key == mid)return mid;else if (key < ST.R[mid].key)high = mid - 1;else//else if (key > ST.R[mid].key)low = mid + 1;   }return 0;
}

PPT上补充:递归实现版本

int Search_bin(SSTable& S, KeyType e, int low, int high)
{if (low > high)return -1;int mid = (high + low) / 2;if (e == S.R[mid].key)return mid;if (e < S.R[mid].key)return Search_bin(S, e, low, mid - 1);elsereturn Search_bin(S, e, mid + 1, high);
}

 平均查找长度推导参考:第五章《树和二叉树》P34

三、分块查找


不考察代码

不过分块查找的代码怎么实现以后有时间倒也可以研究一下,还是挺有意思的

这篇关于数据结构与算法基础(王卓)(28)线性表的查找(2):顺序查找(二分查找、分块查找)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/184699

相关文章

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

0基础租个硬件玩deepseek,蓝耘元生代智算云|本地部署DeepSeek R1模型的操作流程

《0基础租个硬件玩deepseek,蓝耘元生代智算云|本地部署DeepSeekR1模型的操作流程》DeepSeekR1模型凭借其强大的自然语言处理能力,在未来具有广阔的应用前景,有望在多个领域发... 目录0基础租个硬件玩deepseek,蓝耘元生代智算云|本地部署DeepSeek R1模型,3步搞定一个应

Python中顺序结构和循环结构示例代码

《Python中顺序结构和循环结构示例代码》:本文主要介绍Python中的条件语句和循环语句,条件语句用于根据条件执行不同的代码块,循环语句用于重复执行一段代码,文章还详细说明了range函数的使... 目录一、条件语句(1)条件语句的定义(2)条件语句的语法(a)单分支 if(b)双分支 if-else(

关于Spring @Bean 相同加载顺序不同结果不同的问题记录

《关于Spring@Bean相同加载顺序不同结果不同的问题记录》本文主要探讨了在Spring5.1.3.RELEASE版本下,当有两个全注解类定义相同类型的Bean时,由于加载顺序不同,最终生成的... 目录问题说明测试输出1测试输出2@Bean注解的BeanDefiChina编程nition加入时机总结问题说明

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据:本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组(Array)2. 切片(Slice)3. 映射(Map)对比总结注意事项基本概念在 Go 语言中,有三种主要

C++实现封装的顺序表的操作与实践

《C++实现封装的顺序表的操作与实践》在程序设计中,顺序表是一种常见的线性数据结构,通常用于存储具有固定顺序的元素,与链表不同,顺序表中的元素是连续存储的,因此访问速度较快,但插入和删除操作的效率可能... 目录一、顺序表的基本概念二、顺序表类的设计1. 顺序表类的成员变量2. 构造函数和析构函数三、顺序表

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1

MySQL中my.ini文件的基础配置和优化配置方式

《MySQL中my.ini文件的基础配置和优化配置方式》文章讨论了数据库异步同步的优化思路,包括三个主要方面:幂等性、时序和延迟,作者还分享了MySQL配置文件的优化经验,并鼓励读者提供支持... 目录mysql my.ini文件的配置和优化配置优化思路MySQL配置文件优化总结MySQL my.ini文件

JAVA利用顺序表实现“杨辉三角”的思路及代码示例

《JAVA利用顺序表实现“杨辉三角”的思路及代码示例》杨辉三角形是中国古代数学的杰出研究成果之一,是我国北宋数学家贾宪于1050年首先发现并使用的,:本文主要介绍JAVA利用顺序表实现杨辉三角的思... 目录一:“杨辉三角”题目链接二:题解代码:三:题解思路:总结一:“杨辉三角”题目链接题目链接:点击这里