前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >查找算法之折半查找+分块查找

查找算法之折半查找+分块查找

作者头像
跋扈洋
发布2021-09-03 14:10:24
1.6K0
发布2021-09-03 14:10:24
举报
文章被收录于专栏:物联网知识物联网知识

基本概念

  1. 查找表:由同一种类型的数据元素(记录)组成
  2. 静态查找表:只需要查找算法
  3. 动态查找表:除了查找,还需要增删改查数据元素
  4. 关键字:唯一标识数据元素的数据项

常见的查找算法

折半查找

概念

折半查找又称二分查找,仅适用于有序的顺序表,不能用链表。

算法

代码语言:javascript
复制
//查找算法
int binary_search(seqlist L,Elemtype key)
{
int low,high=L.TableLen-1,mid;
while(low<=high)
{
mid=(low<=high)/2;
if(L.elem[mid]==key)
return mid;
else if(L.elem[mid]>key)
high=mid-1;
else
low=mid-1;
}
return -1;
}

折半查找树的构造

  1. 如果当前LOW和HIGH之间有奇数个元素,则MID分割后,左右两部分元素个数相等
  2. 如果当前LOW和HIGH之间有偶数个元素,则MID分割后,左部分比右半部分少一个元素
  3. 折半查找的判定树中,若MID={(LOW=HIGH)/2}向下取整,则对于任何一个节点,必有右子树结点数-左子树结点数=0或1
  4. 折半查找判定树必定是平衡二叉树
  5. 折半查找判定树中,只有最下面一层是不满的,因此元素个数为n时,树高h={log2(n+1)}向下取整
  6. 失败结点:n+1(等于成功节点的空链域数量)

分块查找

分块查找,又称索引顺序查找,算法过程:

  1. 在索引表中确定待查记录所属的分块(可顺序,可折半)
  2. 在块中查找
  3. 若索引表中不包含目标关键字,则折半查找索引表最终停在LOW>HIGH,要在LOW所指分块中查找
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2021-08-07,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 物联网知识 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 基本概念
  • 常见的查找算法
    • 折半查找
      • 概念
      • 算法
      • 折半查找树的构造
    • 分块查找
    领券
    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档