网络推广员,公司网站做优化少钱,wordpress 繁体语言包,郑州服装网站建设文章目录 一.二分查找简介二.二分查找的原理三.如何用C语言实现二分查找 一.二分查找简介
二分查找也称折半查找#xff08;Binary Search#xff09;#xff0c;它是一种效率较高的查找方法。但是#xff0c;折半查找要求线性表必须采用顺序存储结构#xff0c;而且表中… 文章目录 一.二分查找简介二.二分查找的原理三.如何用C语言实现二分查找 一.二分查找简介
二分查找也称折半查找Binary Search它是一种效率较高的查找方法。但是折半查找要求线性表必须采用顺序存储结构而且表中元素按关键字有序排列。
它的优点是查找速度快缺点是待查表为有序表。
二.二分查找的原理
假如要在一个有序数组记为arr[mid]中查找元素a那么可以先找到数组中间的元素记为arr[mid]将将该元素与a比较大小若该元素大于a那么可将该元素的下一项记为最左边的项再将这个最左边的项和最右边的项的中间项与a比较大小以此类推。
三.如何用C语言实现二分查找
如图所示以这样一个有序数组为例来查找数字7
将最左边的元素下标记为left将最右边的元素下标记为right。 首先可以查找最中间的元素记为arr[mid]将它与k即数字7进行比较
若arr[mid] k则将 left 改为 mid 1。 若arr[mid] k则将 right 改为 mid - 1。 若arr[mid] k循环结束。 else if (arr[mid] k) {printf(找到了该元素下标是%d, mid);break;}剩下的思路以此类推即可。 不难得出这可以用一个while循环来实现那么while循环的条件是什么 由上可知left一直在增加而right一直在减少直到最终查找出元素即可若left right且未查找出指定元素时循环继续进行。
while循环如图所示 while (leftright) {int mid (left right) / 2;if (arr[mid] k) {left mid 1;}else if (arr[mid] k) {right mid - 1;}else if (arr[mid] k) {break;}}
若leftright时指定元素还未查找出来则说明该数组不存在该元素。 if (left right) {printf(对不起没有找到该元素);}整体代码如下 int arr[] { 1,2,3,4,5,6,7,8,9,10 };int sz sizeof(arr) / sizeof(arr[0]);int k 7;int left 0;int right sz - 1;while (leftright) {int mid (left right) / 2;if (arr[mid] k) {left mid 1;}else if (arr[mid] k) {right mid - 1;}else if (arr[mid] k) {printf(找到了该元素下标是%d\n, mid);break;}}if (left right) {printf(对不起没有找到该元素\n);}return 0;
