做网站多少钱西宁君博示范,商贸网站源码,WordPress文章添加地图导航,重庆森林经典台词图片目录
一、什么是二分查找
二、算法思想
2.1、概述
2.2、举例
#xff08;1#xff09;查找3#xff08;数组里面存在的数#xff09;
#xff08;2#xff09;查找12#xff08;数组里面不存在的数#xff09;
三、代码实现
四、计算mid公式的优化 一、…目录
一、什么是二分查找
二、算法思想
2.1、概述
2.2、举例
1查找3数组里面存在的数
2查找12数组里面不存在的数
三、代码实现
四、计算mid公式的优化 一、什么是二分查找 二分查找又叫折半查找是一种查找算法它能使查找的速度更快但要求查找的序列必须有序。 如果我们按顺序在一个序列中查找一个数当这个数在靠前的位置查找的速度还好那么当这个数在很靠后的位置呢甚至是一个很长的数组要查找的数是最后一个元素这种情况下查找的速度就很慢了。因此我们需要用更优的二分查找算法。
二、算法思想
2.1、概述 记录数组的三个位置low、high、mid分别记录当前查找的数组子集的起始位置、结束位置、中间位置。当前数组子集的mid (low high) / 2注意C语言中整型数相除结果会舍去小数部分。 每次将要查找的数key与mid位置的数比较如果key大于mid位置的数说明key是在数组右半子集的范围里那么更新子集的范围low更新为mid1如果key小于mid位置的数说明key是在数组左半子集的范围里那么更新子集的范围high更新为mid - 1。 重复上述的过程直到查找到key或者low大于highkey没在数组中结束。
2.2、举例 有序数组如下并标记三个位置 1查找3数组里面存在的数 第一趟3比5小 第二趟3比2大 第三趟3等于mid位置的数3查找成功。
2查找12数组里面不存在的数 第一趟12比5大 第二趟12比8大 第三趟12比9大 第四趟12比10大 low比high大结束查找失败。
三、代码实现 代码中使用sizeof计算len的方法不懂的看这篇文章的“sizeof计算数组的长度”这一部分http://t.csdnimg.cn/wt5LY不懂while里EOF用法的看这篇文章的“scanf的返回值”部分http://t.csdnimg.cn/80wMT。
#define _CRT_SECURE_NO_WARNINGS
#includestdio.hint main() {int arr[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };int len sizeof(arr) / sizeof(arr[0]); //数组的长度int low, high, mid, key;while(scanf(%d, key) ! EOF){ // 控制查找多次low 0;high len - 1;while (low high) {mid (low high) / 2;if (key arr[mid])low mid 1;else if (key arr[mid])high mid - 1;else {printf(查找成功在下标%d处\n, mid);break;}}if (low high)printf(查找失败\n);}return 0;
} 运行结果 四、计算mid公式的优化 当数组很长时low、high很可能是一个很大的数这时候会出现一些问题。用Everthing软件查看一下limits.h头文件里的INT_MAX的值为2147483647假如把low和high都初始化为2147483646看看有什么结果 会发现结果跟我们预期的不一样这是因为数值超过了int类型的长度发生了溢出暂且不深入了解是什么原理。所以需要优化mid的计算方法如下图所示 我们可以把长的与短的做差再将这个差除以2最后将这一半补到短的上面就可以避免加法造成溢出了。因此可以将mid计算公式优化为mid low (high - low) / 2。再运行看看 得到了正确的结果。 有人会想为什么不直接用mid low / 2 high / 2呢因为整除是会舍去小数部分的两次分别做除法舍去的小数部分可能更多误差就更大了。比如3 / 2 5 / 2 3 而(3 5) / 2 4两者结果并不一样。
