集合中查找某个元素并获取元素位置的方法大家可能并不陌生,简单暴力的做法就是用for遍历一遍。不过这样做查找较大集合中元素会耗费时间,影响效率。对于PLC这种单线程的系统来说会大大影响扫描周期,是不能容忍的。
那么有没有方法提高查找效率呢,这就不得不说二分查找。因为高效的查找效率,二分查找算法总能排进计算机十大经典算法
一、二分查找算法原理
一个升序数组分成两半,比较中间值与目标值的大小。如果目标值等于中间值,则查找成功并返回中间值的索引。如果目标值小于中间值,则在数组的左半部分继续查找;反之,则在右半部分继续查找。不断迭代,直到找到目标值或确定目标值不存在于数组中。
二分查找有一个前提条件:数组一定是有序的,即数组中元素按升序或降序排列。
二、二分查找与遍历查找的比较
从二分查找算法原理不难看出二分查找每次迭代都会排除原查找集合的一半,查找效率在迭代中是成指数增长的,对于二分查找算法时间复杂度O=Log n (n=数组中元素个数)。而对于遍历查找,时间复杂度O=n(n=数组中元素个数)。大家可自行计算对有1000个元素的数组进行元素查找两种算法的时间复杂度进行对比,差距是巨大的。这也就是说越庞大的数组二分查找效率优势越明显。
但二分查找也有弱点,就是数组一定要有序,一旦数组无序将会导致严重的错查、漏查。而遍历查找对元素顺序不敏感。
三、PLC程序实现二分查找
1、子程序形参列表和说明:
2、程序源码
第一个Region用于计算不定长数组长度和初始化查找边界。
第二个Region用于数组校验和具体算法实现。
四、程序测试
将子程序在主程序中调用一下后仿真,输入查找目标,发现成功输出了目标索引。
当输入一个数组中没有的元素时,发现索引返回了特定值,并且msg中给与了正确的提示。
当我们输入的两次数组不一致时,msg也给了正确的提示。
五、二分查找扩展
二分查找可以查找有序数组中的相同元素,做法是简单的变换一下源码同时找到有序数组中相同元素最右侧的索引和最左侧索引。源码和以上源码是“瓢”和“葫芦”的关系,笔者这里就不分开写了。
加入知识星球智能制造与自动化,加入会员可下载此公众号发布文章中的相关资料(行业报告、MES、数字化技术方案、自动化教程、自动化行业标准化资料VASS\SICAR\戴姆勒等、C#上位机开发、node-red开发、人工智能教程等)。
今天的文章,如果你感觉有价值,请记得一键三连:点赞加关注,留言,转发朋友圈,分享收藏,点击在看之后,一定记着加我个人微信:ZIDHXB。