精华内容
下载资源
问答
  • 在无序的数组中查找一指定值,必须遍历整个数组,直至查找成功,计算其平均查找次数也相当简单: avg线性 = (1 + n) / 2 因在数组中,各个元素被查找的概率相等,最好的情况是第1个就是目标元素;最坏的情况是...

    *不讨论查找不成功的情况

    *设一数组arr,长度为n(下列例子中,n 取具体值 100, 10000, 10000000)

    线性查找(顺序查找)

    在无序的数组中查找一指定值,必须遍历整个数组,直至查找成功,计算其平均查找次数也相当简单:

    avg线性 = (1 + n) / 2

    因在数组中,各个元素被查找的概率相等,最好的情况是第1个就是目标元素;最坏的情况是最后一个才是目标元素,就不得不遍历整个数组,平均查找次数是线性递增的:

    n = 100,avg线性 = 50.5

    n = 10000,avg线性 = 5000.5

    n = 10000000,avg线性 = 5000000.5

    二分查找

    使用二分查找前,必须先保证数组有序,其每次先把目标元素与位于数组中间的值进行比较(假设数组升序),若目标元素较大(小),则舍弃位于数组中间的左(右)边部分,不再比较左(右)边,再使用二分查找比较剩余部分:

    直至查找成功后停止。

    二分查找的平均查找次数略微复杂:

    avg二分 =  ((n+1)*ceil(log2(n+1)) - 2^ceil(log2(n+1)) + 1)/n,

    分子是全部元素的查找次数总和,分母就是数组大小n,相除即平均查找次数

    ???,怎么来的?

    数组个数 次数总和
    1 1
    2 3(1+2)
    3 5(1+2+2)
    4 8(1+2+2+3)
    5 11(1+2+2+3+3)

    6

    14(1+2+2+3+3+3)

    7 17(1+2+2+3+3+3+3)
    8 21(1+2+2+3+3+3+3+4)
    9 25(1+2+2+3+3+3+3+4+4)
    ... ...

    序列1, 3, 5, 8, 11, 14, 17, 21, 25, ... 可在 OEIS 官网 查询得到

    二分查找平均查找次数呈对数增长(保留两位小数):

    n = 100,avg二分 = 5.8

    n = 10000,avg二分 = 12.36

    n = 10000000,avg二分 = 22.32

    以下给出部分数组大小(图中n列)与平均查找次数(图中approximation列)

    (图片数据来源WolframAlpha

    二者平均查找次数图形比较

    蓝:线性查找

    红:二分查找

    展开全文
  • 浅谈分查找最大次数的理解

    千次阅读 2020-02-17 21:33:37
    首先列出二分查找最大次数的公式 |log2n|+1(|x|为不大于x的最大整数) 接下来谈一谈我的理解: 数组大小 查找的最大次数 1(2^ 0) 1 2(2^1) 2 4(2^2) 3 当数组大小为8时(a[0],a[1]…a[7]),(第一步)对半...

    首先列出二分查找最大次数的公式 |log2n|+1(|x|为不大于x的最大整数)
    接下来谈一谈我的理解:
    数组大小 查找的最大次数
    1(2^ 0) 1
    2(2^1) 2
    4(2^2) 3

    当数组大小为8时(a[0],a[1]…a[7]),(第一步)对半查找取a[3],之后数组划分为a[0],a[1],a[2]和a[4],a[5],a[6],a[7],因为我们要次数最大,因此自然在后者而不是前者中继续查找(毕竟4比3大)。(第二步)对a[4],a[5],a[6],a[7]这4个数进行对半查找,但是这种情况已在上面列出,对于4个长度的数组,我们最大查找次数为3.
    (第三步)将第一步和第二步所进行的次数相加,1+3=4.
    因此当数组长度为8时,查找的最大次数为4.

    同理,数组长度为16时,对半查找一次后情况如同长度为8的数组,英雌查找的最大次数为4+1=5.
    数组大小 查找的最大次数
    由此可得 2^n n+1

    讨论了基本情况之后,我们来讨论更复杂的情况
    假设一个数x,2^n<x,
    x<2^(n+1).
    同样的操作,(第一步)进行对半查找,划分为两个数组,这是一次操作。(第二步)因为x<2^(n+1),所以划分所得到的两个数组,其中最大的一个数组一定小于
    2^(n+1)/2,
    即2^n,因此对其进行对半查找所需的操作次数一定小于n+1,因此等于n(此处假设公式 |log2n|+1成立,由公式 |log2n|+1推出次数等于n).
    (第三步)将第一步和第二步的次数相加得1+n,所以x查找的最大次数与大小为2^n的数组相同,
    可以得到
    数组范围 查找的最大次数
    2的n次方——2的(n+1)次方-1 n+1

    也就是公式 |log2n|+1(|x|为不大于x的最大整数)。

    (ps第一次写博客,写的不好之处还请多多见谅,希望能对大家有点帮助)

    展开全文
  • 查找法的元素查找次数求解

    千次阅读 2014-03-23 21:28:00
    //题目如下://一个长度为20的有序表,采用二分查找进行查找,共有几个元素查找长度为3?/* 10 / \ / \ / \ / \ / \ 5 15 / \
    //题目如下:
    //一个长度为20的有序表,采用二分查找进行查找,共有几个元素查找长度为3?

    //可以构造如下二叉树,进行查找,从1到20均为元素下标。

    //如图可以看出,查找长度为3的分别为元素2,7,12,18

    /*
                10
              /     \
             /       \
            /         \
           /           \
          /             \
         5              15
        /  \          /    \
       /    \        /      \
      2      7     12       18
     / \    / \    / \     /  \
    1   3  6   8  11  13  16  19
         \      \      \   \    \
          4      9      14  17   20
    */


    展开全文
  • 分查找次数

    千次阅读 2017-07-31 17:24:53
    二分法查找数据比较的次数 ---对数   对于有序数组,使用二分法查找数据比较的次数 范围 需要次数 10 4 100 7 1000 10 10000 14 100000 17 1000000 20 除了特别小的数组外,二分法查找表现是...

    二分法查找数据比较的次数 ---对数

     
    对于有序数组,使用二分法查找数据比较的次数
    范围 需要次数
    10 4
    100 7
    1000 10
    10000 14
    100000 17
    1000000 20

    除了对特别小的数组外,二分法查找表现是非常优秀的.
    每次对范围加倍可以创建出一个数列,它是2的幂,假设s表示步数,r表示范围,则有
    r=2s
    当我们知道查找的范围r,求步数s时.就是相当于求某数指数函数的反函数即对数.则公式表示为:
    s=log2(r)
    如何计算呢,大多数计算器都有log功能,通常是以10为底来求对数,但是通过结果乘以3.322可以转换成以2为底的对数
    log10(100)=2;log2(100)=2乘以3.322 = 6.644 四舍五入为7正好是上面数据对照表100对应的7次.
    展开全文
  • 折半查找的平均查找次数分析

    万次阅读 2016-10-24 16:41:40
    前面我们讨论过在有序顺序表的查找树中,是最不平衡树,关键字有n个,则查找失败的结点有n+1个。把这个一般化,性质不变,也即:查找失败结点仍然是n+1个。这个性质在B树部分也是成立的,不做严格推导...总的查找次数
  • 基本思想 首先将给定值K与表中中间位置的关键字比较,若相等,则查找成功,返回该元素的下标;若不等,则所查找的元素只能在中间数据以外前半部分或后半部分。然后在缩小的区间中继续进行同样的...用二分查找...
  • 查找判定树的每个节点的查找次数=该节点所在树的层数 查找成功时的次数不会超过树的深度,假设节点个数为n,那么树的深度为[log2n]+1,其中[log2n]为向下取整 判定树构造 以11个树的列表为例:a=[1,2,3...
  • 分查找法最大最小比较次数

    千次阅读 2019-09-10 11:11:21
    说说「二分查找法」。
  • 分查找的最大比较次数

    千次阅读 2020-04-23 12:18:21
    分查找很简单,可是对于一个区间长度为n的数组,最大的比较次数为多少呢? 对于标准的二分查找,我们每次从区间[l,r)中取一个值,和中间值mid=(l+r)>>1进行比较,然后将数组分为[l,mid) [mid+1,r),即每次将...
  • 分查找过程二分查找,也称折半查找,是有序序列的查找算法,时间复杂度为O(log n).本文的重点是某元素二分查找的比较次数。特别要注意的是查找的上下边界问题(下面有解释)例:22 34 55 77 89 93 99 102 120 ...
  • (2014-1)二分查找的二分次数

    千次阅读 2019-03-02 10:23:42
    那么来计算二次数吧!约定二的中点mid = (left + right) / 2。 输入: 第一行输入一个整数N(N&lt;=10000)。 第二行输入N个升序整数。第三行输入一个待查找的整数(必定在第二行中出现过)。 输出: ...
  • 分查找最大比较次数

    千次阅读 2009-04-26 10:47:30
    有序数组进行查找,一般采用折半查找,也叫二分查找。它的最大比较次数,或者查找一个数组中不存在的数据的最大比较次数,如下:   public class BinarySearchNum { private static int Length = 9; ...
  • 分查找关键码的比较次数

    千次阅读 2019-04-18 10:41:51
    在顺序表 { 12、15、17、20、24、30、38、43、45、51、52} 中,用二分法查找关键码 20需做( ) 次关键字比较。 解: 数值 12 15 17 20 24 30 38 43 45 51 52 下标 0 1 2 3 4 5 6 7 8 9 10 以上一共11个...
  • 顺序查找次数

    千次阅读 2018-09-13 22:36:22
    1.一般线性表的顺序查找 对于有n个元素的线性表,给定值key与表中的第i个元素关键字相等,即为第i个元素时,需要n-i+1次比较。查找成功时,平均查找长度为ASL= *(n-i+1) 当每个元素的概率相同=1/n,则有 ASL= *...
  • 分查找元素求比较次数

    万次阅读 2019-10-16 12:10:33
    在顺序表 { 12、15、17、20、24、30、38、43、45、51、52} 中,用二分法查找关键码 20需做( ) 次关键字比较。 解: 数值 12 15 17 20 24 30 38 43 45 51 52 下标 0 1 2 3 4 5 6 7 8 9 10 ...
  • 分查找(折半查找

    万次阅读 多人点赞 2018-07-21 00:07:47
    分查找是一种算法,其输入是一个有序的元素列表(必须是有序的),如果查找的元素包含在列表中,二分查找返回其位置,否则返回NULL 比如说有一个1-100的数字,我随机的选择其中一个数字(假设为60),你需要以...
  • 代码如下,在计算冲突次数和查找次数的时候,HS.con和count两个变量都不能正确更新,不知道哪里有问题,请教各位大神,谢谢! ``` #include #include #include <string> #include <iomanip> #include using ...
  • =1000)、n个非降序排列的整数以及要查找的数x,使用二分查找算法查找x,输出x所在的下标(0~n-1)及比较次数。若x不存在,输出-1和比较次数。 输入格式: 输入共三行: 第一行是n值; 第二行是n个整数; 第三行是x值...
  • 有序表的索引顺序结构查找次数分析@(算法学习) 为了提高查找效率,65025个元素的有序顺序表建立索引顺序结构,在最好情况下查找到表中已有元素,平均需要执行(B)次关键字比较。 A. 10 B. 14 C. 20 D. ...
  • 查找次数(二分法)

    千次阅读 2019-11-17 10:12:05
    设有100个数据元素,采用二分查找时,最大比较次数为: 分析: 元素要查找到 代码: #include <iostream> using namespace std; int main(){ int a[101]; for(int i=0;i<=100;i++) a[i]=i; int ans; ...
  • 分查找

    千次阅读 2015-10-28 16:08:31
    分查找优点是比较次数少,查找速度快,平均性能好;时间复杂度为O(lgN)。因此二分查找也成为了面试中的常问问题。但是要写出一个完全正确的二分查找并不容易,下面我们先来看个错误的二分查找。(以下大部分是...
  • 分查找算法

    千次阅读 2016-12-25 17:32:17
    为什么要说二算法?...(不要问我为什么会知道,掩面哭泣ing......) 二分查找算法: 二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此
  • 数据结构之折半查找(c语言描述)题目/*题目... 输入若干数据(少于20个且递增有序)和要查找的数据进行折半查找,输出查找成功或不成功比较的次数。 输入描述 在第一行输入若正数,输入-1时结束,在第二行输入要...
  • Round17—顺序查找、二分查找

    千次阅读 2019-11-09 16:37:15
    知道什么是顺序查找,什么是二分查找,知道判定树,知道二分查找的最大比较次数是 单选题: 2-1已知一个长度为16的顺序表L,其元素按关键字有序排列。若采用二分查找查找一个L中不存在的元素,则关键字的比较...
  • python 二分查找

    万次阅读 2019-07-23 16:31:55
    分查找也称折半查找(Binary ...比如说有一个1-100的数字,我随机的选择其中一个数字(假设为10),你需要以最少的次数猜到我所选择的数字,每次猜测后,我会告诉你大了,小了,了。 def B_search(listvar,v...
  • Java实现二分查找

    2014-12-10 17:36:26
    分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。首先,假设表中元素是按升序排列,将表...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 379,184
精华内容 151,673
关键字:

对分查找次数