没有合适的资源?快使用搜索试试~ 我知道了~
折半查找(二分查找)详解
需积分: 0 0 下载量 100 浏览量
2024-01-05
09:52:24
上传
评论
收藏 78KB PDF 举报
温馨提示
试读
1页
折半查找 折半查找(又称二分查找)是一种高效的查找算法,适用于已排序的数组或列表。其基本思想是将待查找的元素与数组中间元素进行比较,如果相等则返回该元素的下标;如果待查找元素小于中间元素,则在数组左半部分继续查找;如果待查找元素大于中间元素,则在数组右半部分继续查找。重复这个过程,直到找到目标元素或者搜索范围为空。 折半查找的时间复杂度为O(log n),其中n为数组长度。因此,折半查找比线性查找和冒泡排序等算法更高效。但是,折半查找要求数组必须是有序的,否则无法使用此算法。
资源推荐
资源详情
资源评论
折半查找(⼆分查找)
折半查找(⼆分查找)
1、折半查找法,也称为⼆分查找法, ⼆分搜索, 是⼀种在有序数组中查找某⼀特定元素的搜索算法.搜索过程中从数组的中间元素开始, 如果中
间元素正好是要查找的元素, 则搜索过程结束;如果某⼀特定元素⼤于或者⼩于中间元素, 则在数组⼤于或⼩⾬元素的那⼀半中查找, ⽽且跟
开始⼀样从中间元素开始⽐较. 若某1个步骤中数组为空, 则代表找不到. 这种搜索算法每⼀次⽐骄傲都使搜索范围缩⼩⼀半.这种⽅法对待查
找的列表有两个要求
必须采⽤顺序存储结构
必须按关键字⼤⼩有序排列
2、折半查找法分析
从定义中可以看出折半查找法有⼏个特性.
(1) 先决条件: 要搜索的数据已经排好序
当然, 怎样将数据排序也是1个算法, 这⾥先不考究了, 但是要使⽤折半查找法, 这个条件是必需满⾜的
(2) 折半查找法适合海量数据查找
折半查找法每执⾏1次.就会抛弃⼀半的⽆⽤数据, 如果数据很少的话,其实⽐线性查找快不了多少, 但是数据量很⼤的话, 抛弃的⼀半⽆⽤数据
就很客观了! 相对于线性查找中节省了这⼀半数据的遍历时间啊.
(3) 折半查找法算法复杂度
假如要查找数据的数量是n, 查找的次数为x,那么查找1次(x=1), 剩下的数据量就是 (n-1)/2 = n/2 -1/2了
当x=2 时 剩下的数据量就是 n/4 - 3/4
当x=3 时 剩下的数据量就是 n/8 - 7/8
所以剩下的数据量R = n/2^x - 1 + 1/2^x
当x很⼤时, R就~= n/2^x -1 了
那么什么时候才会肯定会找出要找的数据呢, 或者缺认该数据不存在呢.
就是当剩余的数据量R=0 时啊.
这时 n/2^x -1 =0 => 2^x = n => x= log2^n (底为2,幂为n的对数)
所以算法复杂度就是 O(log2^n)
⽐起线性查找的算法复杂度O(n) , 优胜很多了.(如果n很⼤的话)
3、具体代码实现:
#include<stdio.h>
int main()
{
int array[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int left = 0,right = 9;
int mid = 0;
int x = 0;
printf("%d", x);
while (left <= right)
{
mid = (left + right) / 2;
if (x < mid)
{
right = mid;//
还会有在此处为
right=mid-1;
这样的输⼊,两种输⼊相同
}
else if (x > mid)
{
left = mid+1;
}
else
{
printf("找到%d了", x);
break;
}
}
}
资源评论
RDSunday
- 粉丝: 232
- 资源: 171
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功