上海小学网站建设招标,电器 东莞网站建设,window服务器如何做网站访问,宿迁宿豫网站建设大家好#xff01;我又来了#xff0c;哈哈~今天我要和大家分享一种神奇的算法——二分查找#xff01;你可能会问#xff0c;“二分查找有什么好玩的#xff1f;”但在我看来它就像一场魔法表演#xff0c;当你输入一个数#xff0c;他会在一堆数中快速找到它的位置。找… 大家好我又来了哈哈~今天我要和大家分享一种神奇的算法——二分查找你可能会问“二分查找有什么好玩的”但在我看来它就像一场魔法表演当你输入一个数他会在一堆数中快速找到它的位置。找不到他还会告诉你这个数不存在数堆中。当然初学C语言的朋友也不要被它的名字所吓到接下来我将详细的告诉你二分查找原理及实现初学C的朋友赶快来学习一波吧 我们前边已经学习了循环在一个数组中查找一个数我们可以使用循环遍历直到找到目标数。但在数据较多的时候一直这样循环的去找就会大大影响程序效率这时我们就有了引进了新的方法来改变效率低的问题那就是我们今天要讲的二分查找。
二分查找的原理 举个栗子假如你一个朋友他买了一双新鞋你问他多少money他告诉你不超过1000那你会怎么猜从1块2块3块……这样的猜吗这样肯定不合适那最快的方法就是区间对半的去猜你说500他说猜小了那么这时区间就减少了一半你再猜750……就这样一直将区间对半排除的去猜你就可以在最少的猜测次数内猜到答案。这也就是二分查找的原理。
适用情况
既然二分查找这么厉害当然它也不是什么情况都能应对的二分查找只适用于有序的的数据查找可以是递增也可以是递减。
如何实现
我们以及知道了原理那么要怎样去实现呢 以上图为例我们创建3个变量分别记录数组的最左下标中间下标最右下标。初始情况下left下标为0mid下标为4right下标为9假设我们要查找的数字是7
假设第一次输入5会收到提示 猜小了 这时查找区间就减少了一半左下标left也就变为了mid1此时left下标为5而mid是左下标和右下标之间的中间下标这时mid就变成了7( (59)/7这里是整除哦如下图 假设第二次输入8收到提示 猜大了 右下标right也就变成了mid-1此时right下标为6mid就变成了5如下图 这时就剩下了两个数
假设第三次输入6继续收到提示 猜小了 left就变成了mid16mid66/26最后就只剩下了一个7。
最后输入7提示“找到了下标为6”。
代码实现二分查找的整体思路大概就是以上这样
代码实现
接下来我们进行代码实现
#includestdio.h
int main()
{int arr[] { 1,2,3,4,5,6,7,8,9,10 };int k 7;int sz sizeof(arr) / sizeof(arr[0]);int right sz - 1;int left 0;int flag 0;while (left right) {int mid (left right) / 2;if (arr[mid] k) {printf(找到了下标是%d,mid);flag;break;}else if (arr[mid] k) {right mid - 1;}else {left mid 1;}}if (flag 0)printf(没找到\n);return 0;
}
好了本期内容到这里就结束了希望对你所帮助感谢阅读我们下期再见
