查找——折半查找(原理)

文章目录折半查找算法原理有关折半查找涉及到的理论计算1、求平均查找长度(ASL)2、求某个关键字的比较(查找)次数&&列出某个关键字将依次与序列中的哪些元素进行比较 折半查找算法原理 别名：二分查找要求线性表是有序表查找思路：设R[low,…,high]是当前的非空查找索引区间(下界为low，上界为high)，首先确定该区间的中间位置mid，mid=(low+high)/2。(向下取整 0 Comments

文章目录

    • 折半查找算法原理
    • 有关折半查找涉及到的理论计算
      • 1、求平均查找长度(ASL)
      • 2、求某个关键字的比较(查找)次数&&列出某个关键字将依次与序列中的哪些元素进行比较

折半查找算法原理

  • 别名：二分查找
  • 要求线性表是有序表
  • 查找思路：设R[low,…,high]是当前的非空查找索引区间(下界为low，上界为high)，首先确定该区间的中间位置mid，mid=(low+high)/2。(向下取整)然后将待查的k值与R[mid].key进行比较：
        若：k=R[mid].key，则查找成功。
        若：k<R[mid].key，确定新的查找索引区间为[low,…,mid-1]。继续在新的索引区间进行折半查找。直到k=R[mid].key为止。
        若：k<R[mid].key，确定新的查找索引区间为[mid+1,…,high]。继续在新的索引区间进行折半查找。直到k=R[mid].key为止。

【例题】

有关折半查找涉及到的理论计算

1、求平均查找长度(ASL)

2、求某个关键字的比较(查找)次数&&列出某个关键字将依次与序列中的哪些元素进行比较

本文链接：https://my.lmcjl.com/post/4379.html

展开阅读全文

相关文章

4 评论

留下您的评论.