1.折半查找的定义:

在计算机中,折半查找,也称二分搜索。它是一种在有序数组中查找某一特定元素的搜索算法。

2.折半查找的实现原理:        

        
搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。
这种搜索算法每一次比较都使搜索范围缩小一半 。

以下是折半查找和顺序遍历的算法实实现动态图

 

3.折半查找算法优点:

折半查找法的优点是比较次数少,查找速度快,平均性能好;

其缺点是要求待查表为有序表,且插入删除困难。

因此,折半查找方法适用于不经常变动而查找频繁的有序列表。

4.代码实现:

# include<stdio.h> # include<string.h> int main() { int arr[] = {
1,2,3,4,5,6,7,8,9,10 };//下标:0,1,2,3,4,5,6,7,8,9 int k = 8; int left = 0; int sz
= sizeof(arr) / sizeof(arr[0]); int right = sz - 1; while (left <= right) { int
mid = (left + right) / 2; if (arr[mid] > k){ right = mid - 1; } else if
(arr[mid] < k){ left = mid + 1; } else{ printf("找到了:%d\n", mid); break; } } if
(left > right)//情况四:找不到 { printf("找不到了\n"); } return 0; }
        代码讲解:       

         1.通过建立左下标left与右下标right组成一个完整的范围。

         2.创建关键查找数k,作为范围内要被查找的数字。

         3. int mid = (left + right) / 2;这句是折半查找的核心语句
,作用就是计算两边元素之和除2(为中间元素)与要查找的元素做对比,进而确定查找数的范围。

         4.if (arr[mid] > k)表示
情况一:求出的中间数若>要查找的数,就将右下标移位到mid的左边一位,直接消去其中一半,之后再求出左下标与更新的右下标的中间元素,更新出新的范围,再与要找元素重新进行对比。

        5.else if (arr[mid] < k)表示情况二:求出的中间数若
<要查找的数,就将左下标移位到mid的右边一位,直接消去其中一半,之后再求出左下标与更新的右下标的中间元素,更新出新的范围,再与要找元素重新进行对比。

        6.else表示情况三:若恰好相等,则直接跳出循环,printf打印输出。

        7.if (left > right)表示情况四:找不到。

        

函数版:优化了一下
#include<stdio.h> #include<String.h> int test(int arr[], int sz, int k) { int
left = 0; int right = sz - 1; while (left <= right) { int mid = (left + right)
/ 2; if (arr[mid] > k) right = mid - 1; else if (arr[mid] < k) left = mid + 1;
else return mid; } if (left > right)//情况四:找不到 return -1; } int main() { int
arr[] = { 1,2,3,4,5,6,7,8,9,10 };//下标:0,1,2,3,4,5,6,7,8,9 int k = 0;
scanf("%d", &k); int sz = sizeof(arr) / sizeof(arr[0]); int ret = test(arr, sz,
k); if (ret == -1) { printf("未找到该元素,该元素不存在!\n"); } else {
printf("找到了,该元素下标处于:%d的位置", ret); } return 0; }
   

技术
今日推荐
PPT
阅读数 89
下载桌面版
GitHub
百度网盘(提取码:draw)
Gitee
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:766591547
关注微信