建设外贸商城网站,太仓网络公司,网站建设平台分析,中国最好的编程学校个人主页#xff1a;【#x1f60a;个人主页】 系列专栏#xff1a;【❤️我欲修仙】 学习名言#xff1a;临渊羡鱼,不如退而结网——《汉书董仲舒传》 系列文章目录
第一章 ❤️ 二分查找 文章目录系列文章目录前言#x1f697;#x1f697;#x1f697;二分查找… 个人主页【个人主页】 系列专栏【❤️我欲修仙】 学习名言临渊羡鱼,不如退而结网——《汉书董仲舒传》 系列文章目录
第一章 ❤️ 二分查找 文章目录系列文章目录前言二分查找第一阶段 二分查找第二阶段 易错点问题一问题二总结题目代码C语言实现前言
经历了一段时间的《数据结构与算法》学习你已经从凡人步入了修仙界现在你可以尝试去接触一些简单的算法题开始你的修仙生涯了那今天我们来看看今天的修炼吧⛽⛽⛽ 这是是一道非常经典的入门级修炼功法收录在力扣# 704而它的名字就已经将写法写在你的脸上了——二分查找 ps:工欲善其事必先利其器一部好的功法可以让你在修仙路上少走许多弯路。 二分查找 二分查找又称折半查找优点是比较次数少查找速度快平均性能好占用系统内存较少;其缺点是要求待查表为有序表且插入删除困难。因此折半查找方法适用于不经常变动而查找频繁的有序列表。首先假设表中元素是按升序排列将表中间位置记录的关键字与查找关键字比较如果两者相等则查找成功;否则利用中间位置记录将表分成前、后两个子表如果中间位置记录的关键字大于查找关键字则进一步查找前一子表否则进一步查找后一子表。重复以上过程直到找到满足条件的记录使查找成功或直到子表不存在为止此时查找不成功。 第一阶段 二分查找 二分查找的基本思想是将n个元素分成大致相等的两部分取a[n/2]与x做比较如果xa[n/2],则找到x,算法中止;如果xa[n/2],则只要在数组a的左半部分继续搜索x,如果xa[n/2],则只要在数组a的右半部搜索x. 因此我们需要left变量middle变量right变量以及以各target变量 在这个阶段我们需要了解二分查找的基本运算方式以及需要使用的变量。
第二阶段 易错点
我们应该了解下二分算法的易错点 1.在循环体的跳出判定条件是左边大于等于右边leftright还是左边大于右边leftright 2.如果(str[middle]target)那么接下来我们应该将middle更新为right还是right-1? 问题一 对待该问题我们需要首先将题意理解清楚我们根据查找区间分为两种写法——左闭右闭写法和左必右开写法 左闭右闭写法故名思意在该区间我们两头的数都应该取到我们假设一个这样的区间[1,1]很明显我们的判定条件上必须加上等于与之相反的当区间为[1,1)左闭右开时我们不能加上等于号。 问题二 应对第二个问题我们只需简单的假设一下当我们使用左闭右闭写法时我们已经判断了(str[middle]target)那么我们下一次判断的时候就不用该将middle加入进去那么自然我们会将right更新为middle-1当我们使用左闭右开写法时本来定义中就已经不包含middle值那么我们为啥还要将right更新为middle-1呢 总结 简单总结一下 左闭右闭写法——要等于号并且middle应更新为leftright1或rightmiddle-1 左闭右开写法——不要等于号并且middle应更新为rightmiddle和(leftmiddle1)(这个地方要好好理解下哟) 题目代码C语言实现
#includestdio.h
#includestring.h
#define MAX 100000
int search(int* nums, int numsSize, int target)
{int left0, right, middle;right numsSize;while (left right)//这里是左闭右闭写法{middle (left right) / 2;if (*(nums middle) target)right middle - 1;else if (*(nums middle) target)left middle 1;elsereturn middle;}return -1;//查找失败无该目标值
}
int main()
{int nums[MAX] { 0 };int target 0;int numsSize 0, i;scanf(%d, numsSize);//输入区间长度printf(\n);for (i 0;i numsSize;i)scanf(%d, nums i);//输入查找区间printf(\n);scanf(%d, target);//输入目标值numsSize strlen(nums);printf(下标为%d, search(nums,numsSize,target));}
