摘要:目录简单原理代码实现简单原理想必学过语言的各位都听说过二分查找的算法,今天我就给各位萌新介绍一下二分查找的简单原理和代码实现。
想必学过C语言的各位都听说过二分查找的算法,今天我就给各位萌新介绍一下二分查找的简单原理和代码实现。
我们使用数组的方式实现二分查找的目标,我们取一串有序数组的中间数组元素,再将此数组元素大小与查找数组比较,再判断是否找到和下一查找区间。使用这种方式可以大大提高我们算法的效率,相比与遍历数组的方法减少了查找次数,也减少了查找时间。下面我们介绍具体代码实现。
我们先设置一个有序数组,如下所示
int arr[] = { 1,2,3,4,5,6,7,8,9,10,11,12,13 };
接下来我们利用sizeof的方式算出数组长度大小,并且初始第一次查找的下标left和right(注意,最后一个数组下标为数组长度-1),如下图所示
int sz = sizeof(arr) / sizeof(arr[0]); int left = 0; int right = sz - 1;
我们再设置一个mid值,作为与被查找数据比较的对象,我们在循环体中将这个值赋为(left+right)/2。重点!!重点!!重点!!我们将两者比较后需要调整left和right的值。若查找数值与mid相等,则此mid下标就是需要查找数值的位置,若查找数值大于mid,我们将left重新赋值为mid+1,若查找数值小于mid,则将right赋值为mid-1,我们将此算法用在一个while循环中,若left<=right证明数组中还存在待查找元素,所以我们使用这一条件作为循环判断条件。下面是全部代码。
int main(){ int arr[] = { 1,2,3,4,5,6,7,8,9,10,11,12,13 }; int sz = sizeof(arr) / sizeof(arr[0]); int left = 0; int right = sz - 1; int a = 0; int mid = 0; scanf("%d", &a); while (left <= right) { mid = (right + left) / 2; if (a > arr[mid]) left = mid + 1; if (a < arr[mid]) right = mid - 1; if(a==arr[mid]) { printf("找到了,下标是%d", mid); break; } } if (left > right) printf("找不到了"); return 0;}
感谢大家的阅读,欢迎各位点赞评论,互关互助,有赞必回,祝各位万事如意。
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/124775.html
摘要:正文二分查找关于二分查找法二分查找法主要是解决在一堆数中找出指定的数这类问题。用二分查找法找寻上界与精确查找不同之处在于,精确查找分成三类大于,小于,等于目标数。 由一道题目引出的: 题目描述 给定一个有序的数组,查找某个数是否在数组中,请编程实现。 分析与解法 一看到数组本身已经有序,我想你可能反应出了要用二分查找,毕竟二分查找的适用条件就是有序的。那什么是二分查找呢? 二分查找可以...
摘要:对于大数据量,则可以用二分查找进行优化。有一个模块,用于维护有序列表。和用于指定列表的区间,默认是使用整个列表。模块提供的函数可以分两类只用于查找,不进行实际的插入而则用于实际插入。 Python 的列表(list)内部实现是一个数组,也就是一个线性表。在列表中查找元素可以使用 list.index() 方法,其时间复杂度为O(n)。对于大数据量,则可以用二分查找进行优化。二分查找要求...
摘要:所以,二分查找较适用于一次排序,多次查找的数据。面对大量的数据,二分查找方能体现其优势。 1. 二分查找的思想 二分查找是一种使用十分普遍的查找算法,其基本的思路也非常的简单,在一个有序的数据集合中,我们想要查找某个数据,直接取最中间的那个数据,将它和要找的数据进行比较,如果较大,则在更大的那个数值区间继续取中间值查找,反之亦然。 例如我们要在一个有序的集合里[1,3,5,6,7,8,...
阅读 1396·2021-11-24 09:39
阅读 3685·2021-11-24 09:39
阅读 1859·2021-11-16 11:54
阅读 1462·2021-09-30 09:47
阅读 1711·2021-09-26 10:16
阅读 2341·2021-09-22 15:33
阅读 1451·2021-09-14 18:01
阅读 2434·2021-09-07 09:59