精华内容
下载资源
问答
  • 看到这个标题无论你是处于怎样的心理进来看了,我觉得是值得的。...既然很简单,那么我们开始一起写一个吧,要求是对num[]={1,2,2,4,4,8,10}不序列在区间[0,7)进行查找,当然我们首先保证要查找的e满足:num[0]

     看到这个标题无论你是处于怎样的心理进来看了,我觉得都是值得的。因为这个问题太简单,任何一个开始接触“真正”算法基本都是从二分查找开始的。至于二分查找都不知道是什么的可以先去找别的资料看下,再来看这篇文章。既然很简单,那么我们开始一起写一个吧,要求是对num[]={1,2,2,4,4,8,10}不减序列在区间[0,7)进行查找,当然我们得首先保证要查找的数e满足:num[0] <= e <= num[0],这个是很容易做到的,为了简化又不失去代表性,e选取2、3、4这三个数。我们就一起开始写吧:

           首先,很容易的写下 int bSearch(int begin, int end, int e)

           然后,很自然的定义 int mid, left = begin, right = end;

           接下来怎么写呢?while(left < right)?while(left <= right)?while(mid == left)?while(mid == right)?………………真正一个写程序人会想纠结好一会儿,我们就选一个吧while(left < right)

           下面,也很自然,min = (left + right) >> 1; 用位云算能节省一些时间呢!

            现在呢?又是纠结的时候了吧?if(num[mid] > e)?if(num[mid] >= e)?我们也随便选一个吧,if(num[mid] > e)

            其实,下面你会不断纠结……right = mid;这是正常人的写法,但是有时候也会看到别人写成right = mid - 1;我们也考虑下吧,但是现在我们就直接写right = mid;

            有if了当然也会有else,然后理所当然 left = mid;同样记住还有一个选择left = mid + 1;


    不错,整个while循环搞定了,最后就是返回了,写下return的时候是不是又纠结了?left?right?mid?算了,就写mid吧,整个程序就写好了,如下:

    1. int bSearch(int begin, int end, int e)  
    2. {  
    3.     int mid, left = begin, right = end;  
    4.     while(left < right)  
    5.     {  
    6.         mid = (left + right) >> 1;  
    7.         if(num[mid] > e) right = mid;  
    8.         else left = mid;  
    9.     }  
    10.     return mid;  
    11. }  

     补充好整个程序后运行吧!查找2、3、4的时候都没有结果出现!!比如查4的时候,单步调试会发现当mid=4,left=4,right=5,接下来就一直在while里循环,保持不变!问题到底在哪?问题在很多地方,因为我们上面的遇到很多选择,没有结果是多个选择作用的共同的结果,通过修修补补也可以得到想要的结果,其它例子就不举了,直接说说本文章讨论的关键吧。我总结的二分无非就4种情况:YES_LEFT、YES_RIGHT、NO_LEFT、NO_RIGHT,分别代表:能找到且返回最左边的数的位置(如查找4的时候返回位置3)、能找到且返回最右边的数的位置(如查找4的时候返回位置4)、不能找到且返回左边与其接近的数的位置(如查找3的时候返回位置2)、不能找到且返回右边与其接近的数的位置(如查找3的时候返回位置3)。下面是我总结调试的代码:


    对于YES_LEFT或者NO_RIGHT

    1. int bSearch(int begin, int end, int e)  
    2. {  
    3.     int mid, left = begin, right = end;  
    4.     while(left <= right)  
    5.     {  
    6.         mid = (left + right) >> 1;  
    7.         if(num[mid] >= e) right = mid - 1;  
    8.         else left = mid + 1;  
    9.     }  
    10.     return left;  
    11. }  
    对于YES_RIGHT或者NO_LEFT

    1. int bSearch(int begin, int end, int e)  
    2. {  
    3.     int mid, left = begin, right = end;  
    4.     while(left <= right)  
    5.     {  
    6.         mid = (left + right) >> 1;  
    7.         if(num[mid] > e) right = mid - 1;  
    8.         else left = mid + 1;  
    9.     }  
    10.     return right;  
    11. }  

          不做过多说明,单步调试自然会发现执行过程,要说明的是,两个程序都用了right = mid - 1; left = mid +1;用这个的前提是终止条件要是left <= right。要注意的是,有的二分查找不是只需要四种情况中的一种,而是组合使用,比如查找一个数,如果找到则×××不然则×××,如果是YES_LEFT || NO_RIGHT组合或者YES_RIGHT || NO_LEFT组合就直接用上面代码即可,否则就要综合用了,加一些判断等说明,因为用的时候不多,就不给出代码了,自己如果遇到可以试着写写,当成模板,以后直接用~

           现在,是不是觉得二分查找很容易呢?如果总结过的话……




    引用请注明出处:http://blog.csdn.net/int64ago/article/details/7425727


    二分查找的基本思想是将n个元素分成大致相等的两部分,去a[n/2]与x做比较,如果x=a[n/2],则找到x,算法中止;如果x<a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x.

    时间复杂度无非就是while循环的次数!

    总共有n个元素,

    渐渐跟下去就是n,n/2,n/4,....n/2^k,其中k就是循环的次数

    由于你n/2^k取整后>=1

    即令n/2^k=1

    可得k=log2n,(是以2为底,n的对数)

    所以时间复杂度可以表示O()=O(logn)

    展开全文
  • 扩展:判断一个数值是不是2整数次方,如果是的话,这个的二进制中有且只有一个1,那么这个n会有 n&(n-1) == 0。或者求两个整数m和n需要改变m二进制中的多少位才能得到n,可以先做 m^n 的异或运算,然后...
  • 二分查找算法

    2016-08-18 16:02:07
    看到这个标题无论你是处于怎样的心理进来看了,我...既然很简单,那么我们开始一起写一个吧,要求是对num[]={1,2,2,4,4,8,10}不序列在区间[0,7)进行查找,当然我们首先保证要查找的e满足:num[0] <= e <...

    看到这个标题无论你是处于怎样的心理进来看了,我觉得都是值得的。因为这个问题太简单,任何一个开始接触“真正”算法基本都是从二分查找开始的。至于二分查找都不知道是什么的可以先去找别的资料看下,再来看这篇文章。既然很简单,那么我们开始一起写一个吧,要求是对num[]={1,2,2,4,4,8,10}不减序列在区间[0,7)进行查找,当然我们得首先保证要查找的数e满足:num[0] <= e <= num[0],这个是很容易做到的,为了简化又不失去代表性,e选取2、3、4这三个数。我们就一起开始写吧:

           首先,很容易的写下 int bSearch(int begin, int end, int e)

           然后,很自然的定义 int mid, left = begin, right = end;

           接下来怎么写呢?while(left < right)?while(left <= right)?while(mid == left)?while(mid == right)?………………真正一个写程序人会想纠结好一会儿,我们就选一个吧while(left < right)

           下面,也很自然,min = (left + right) >> 1; 用位云算能节省一些时间呢!

            现在呢?又是纠结的时候了吧?if(num[mid] > e)?if(num[mid] >= e)?我们也随便选一个吧,if(num[mid] > e)

            其实,下面你会不断纠结……right = mid;这是正常人的写法,但是有时候也会看到别人写成right = mid - 1;我们也考虑下吧,但是现在我们就直接写right = mid;

            有if了当然也会有else,然后理所当然 left = mid;同样记住还有一个选择left = mid + 1;

     

    不错,整个while循环搞定了,最后就是返回了,写下return的时候是不是又纠结了?left?right?mid?算了,就写mid吧,整个程序就写好了,如下:

     

    [cpp] view plain copy  print?

    1. int bSearch(int begin, int end, int e)  
    2. {  
    3.     int mid, left = begin, right = end;  
    4.     while(left < right)  
    5.     {  
    6.         mid = (left + right) >> 1;  
    7.         if(num[mid] > e) right = mid;  
    8.         else left = mid;  
    9.     }  
    10.     return mid;  
    11. }  

     

           补充好整个程序后运行吧!查找2、3、4的时候都没有结果出现!!比如查4的时候,单步调试会发现当mid=4,left=4,right=5,接下来就一直在while里循环,保持不变!问题到底在哪?问题在很多地方,因为我们上面的遇到很多选择,没有结果是多个选择作用的共同的结果,通过修修补补也可以得到想要的结果,其它例子就不举了,直接说说本文章讨论的关键吧。我总结的二分无非就4种情况:YES_LEFT、YES_RIGHT、NO_LEFT、NO_RIGHT,分别代表:能找到且返回最左边的数的位置(如查找4的时候返回位置3)、能找到且返回最右边的数的位置(如查找4的时候返回位置4)、不能找到且返回左边与其接近的数的位置(如查找3的时候返回位置2)、不能找到且返回右边与其接近的数的位置(如查找3的时候返回位置3)。下面是我总结调试的代码:

     

    对于YES_LEFT或者NO_RIGHT

     

    [cpp] view plain copy  print?

    1. int bSearch(int begin, int end, int e)  
    2. {  
    3.     int mid, left = begin, right = end;  
    4.     while(left <= right)  
    5.     {  
    6.         mid = (left + right) >> 1;  
    7.         if(num[mid] >= e) right = mid - 1;  
    8.         else left = mid + 1;  
    9.     }  
    10.     return left;  
    11. }  

    对于YES_RIGHT或者NO_LEFT

     

     

    [cpp] view plain copy  print?

    1. int bSearch(int begin, int end, int e)  
    2. {  
    3.     int mid, left = begin, right = end;  
    4.     while(left <= right)  
    5.     {  
    6.         mid = (left + right) >> 1;  
    7.         if(num[mid] > e) right = mid - 1;  
    8.         else left = mid + 1;  
    9.     }  
    10.     return right;  
    11. }  

     

          不做过多说明,单步调试自然会发现执行过程,要说明的是,两个程序都用了right = mid - 1; left = mid +1;用这个的前提是终止条件要是left <= right。要注意的是,有的二分查找不是只需要四种情况中的一种,而是组合使用,比如查找一个数,如果找到则×××不然则×××,如果是YES_LEFT || NO_RIGHT组合或者YES_RIGHT || NO_LEFT组合就直接用上面代码即可,否则就要综合用了,加一些判断等说明,因为用的时候不多,就不给出代码了,自己如果遇到可以试着写写,当成模板,以后直接用~

           现在,是不是觉得二分查找很容易呢?如果总结过的话……

    展开全文
  • 看到这个标题无论你是处于怎样的心理进来看了,我觉得是值得的。...既然很简单,那么我们开始一起写一个吧,要求是对num[]={1,2,2,4,4,8,10}不序列在区间[0,7)进行查找,当然我们首先保证要查找的e满足:num[0]


     

    看到这个标题无论你是处于怎样的心理进来看了,我觉得都是值得的。因为这个问题太简单,任何一个开始接触“真正”算法基本都是从二分查找开始的。至于二分查找都不知道是什么的可以先去找别的资料看下,再来看这篇文章。既然很简单,那么我们开始一起写一个吧,要求是对num[]={1,2,2,4,4,8,10}不减序列在区间[0,7)进行查找,当然我们得首先保证要查找的数e满足:num[0] <= e <= num[0],这个是很容易做到的,为了简化又不失去代表性,e选取2、3、4这三个数。我们就一起开始写吧:

           首先,很容易的写下 int bSearch(int begin, int end, int e)

           然后,很自然的定义 int mid, left = begin, right = end;

           接下来怎么写呢?while(left < right)?while(left <= right)?while(mid == left)?while(mid == right)?………………真正一个写程序人会想纠结好一会儿,我们就选一个吧while(left < right)

           下面,也很自然,min = (left + right) >> 1; 用位云算能节省一些时间呢!

            现在呢?又是纠结的时候了吧?if(num[mid] > e)?if(num[mid] >= e)?我们也随便选一个吧,if(num[mid] > e)

            其实,下面你会不断纠结……right = mid;这是正常人的写法,但是有时候也会看到别人写成right = mid - 1;我们也考虑下吧,但是现在我们就直接写right = mid;

            有if了当然也会有else,然后理所当然 left = mid;同样记住还有一个选择left = mid + 1;


    不错,整个while循环搞定了,最后就是返回了,写下return的时候是不是又纠结了?left?right?mid?算了,就写mid吧,整个程序就写好了,如下:

    int bSearch(int begin, int end, int e)  
    {  
        int mid, left = begin, right = end;  
        while(left < right)  
        {  
            mid = (left + right) >> 1;  
            if(num[mid] > e) right = mid;  
            else left = mid;  
        }  
        return mid;  
    }  

    补充好整个程序后运行吧!查找2、3、4的时候都没有结果出现!!比如查4的时候,单步调试会发现当mid=4,left=4,right=5,接下来就一直在while里循环,保持不变!问题到底在哪?问题在很多地方,因为我们上面的遇到很多选择,没有结果是多个选择作用的共同的结果,通过修修补补也可以得到想要的结果,其它例子就不举了,直接说说本文章讨论的关键吧。我总结的二分无非就4种情况:YES_LEFT、YES_RIGHT、NO_LEFT、NO_RIGHT,分别代表:能找到且返回最左边的数的位置(如查找4的时候返回位置3)、能找到且返回最右边的数的位置(如查找4的时候返回位置4)、不能找到且返回左边与其接近的数的位置(如查找3的时候返回位置2)、不能找到且返回右边与其接近的数的位置(如查找3的时候返回位置3)。下面是我总结调试的代码:

    对于YES_LEFT或者NO_RIGHT

    nt bSearch(int begin, int end, int e)  
    {  
        int mid, left = begin, right = end;  
        while(left <= right)  
        {  
            mid = (left + right) >> 1;  
            if(num[mid] > e) right = mid - 1;  
            else left = mid + 1;  
        }  
        return left;  
    }  

    对于YES_RIGHT或者NO_LEFT

    int bSearch(int begin, int end, int e)  
    {  
        int mid, left = begin, right = end;  
        while(left <= right)  
        {  
            mid = (left + right) >> 1;  
            if(num[mid] > e) right = mid - 1;  
            else left = mid + 1;  
        }  
        return right;  
    }  

    不做过多说明,单步调试自然会发现执行过程,要说明的是,两个程序都用了right = mid - 1; left = mid +1;用这个的前提是终止条件要是left <= right。要注意的是,有的二分查找不是只需要四种情况中的一种,而是组合使用,比如查找一个数,如果找到则×××不然则×××,如果是YES_LEFT || NO_RIGHT组合或者YES_RIGHT || NO_LEFT组合就直接用上面代码即可,否则就要综合用了,加一些判断等说明,因为用的时候不多,就不给出代码了,自己如果遇到可以试着写写,当成模板,以后直接用~

           现在,是不是觉得二分查找很容易呢?如果总结过的话……

    引用请注明出处:http://blog.csdn.net/int64ago/article/details/7425727



    展开全文
  • 本附录讨论八进制、十六进制和二进制。 附录B:C++保留字 本附录列出了C++关键字。 附录C:ASCII字符集 本附录列出了ASCII字符集及其十进制、八进制、十六进制和二进制表示。 附录D:操作符优先级 本...
  • 本附录讨论八进制、十六进制和二进制。 附录B:C++保留字 本附录列出了C++关键字。 附录C:ASCII字符集 本附录列出了ASCII字符集及其十进制、八进制、十六进制和二进制表示。 附录D:操作符优先级 本...
  • 本附录讨论八进制、十六进制和二进制。 附录B:C++保留字 本附录列出了C++关键字。 附录C:ASCII字符集 本附录列出了ASCII字符集及其十进制、八进制、十六进制和二进制表示。 附录D:操作符优先级 本...
  • <code>0.1和<code>0.2的二进制浮点表示不是精确的ÿ0c;所以相加后不是<code>0.3</code>ÿ0c;接近(不等于)<code>0.30000000000000004。 所以ÿ0c;比较数字时ÿ0c;应该有个宽容值。ES6中...
  • java基础入门教程

    热门讨论 2009-04-29 21:36:10
    由 于 各 界 看 好 它 ,因 此 ,各 大 公 司 纷 纷 表 示 支 持 Java,Inte l、 Xerox公 司 声 言将 把 Java嵌 入 到 他 们 的 产 品 中 去 。 就 连 华尔 街 金 融 界 也 在 投入 资 金 人 力 用 Java开 发 电 ...
  • 注意: 一个字节的 8 位 D7、 至 D0, D6 分别输出到 P3.7、 P3.6 至 P3.0, 比如 P3=0x0f, P3.7、 则 P3.6、 P3.5、P3.4 四个引脚输出低电平,而 P3.3、P3.2、P3.1、P3.0 四个引脚输出高电平。同样,输入 一...
  • 魔兽世界(修订版)

    2017-02-06 07:45:54
    但是若生命值9后会小于等于0,则生命值不9,而是变为1。即iceman不会因走多了而死。 lion 若是战死,则其战斗前的生命值就会转移到对手身上。 在一个 wolf 通过主动攻击杀死敌人的次数达到偶数的时刻(次数从...
  • noip提高组试题

    2018-07-12 10:44:30
    编译命令(不包含任何优化开关) 对于 C++语言 g++ -o factor factor.cpp -lm g++ -o qc qc.cpp –lm g++ -o bus bus.cpp -lm 对于 C 语言 gcc -o factor factor.c -lm gcc -o qc qc.c –lm gcc -o bus bus.c -lm ...
  • 设p为指针变量,则p==0表明p是空指针,它不指向任何变量;p!=0表示p不是空指针。空指针是由对指针变量赋予0值而得到的。例如: #define NULL 0 int *p=NULL; 对指针变量赋0值和不赋值是不同的。指针变量未赋值时,...
  • excel的使用

    2012-11-25 17:06:01
    (1) 分数的输入如果直接输入“1/5”,系统会将其变为“1月5日”,解决办法是:先输入“0”,然后输入空格,再输入分数“1/5”。(2) 序列“001”的输入如果直接输入“001”,系统会自动判断001为数据1,解决办法...
  • LINGO软件的学习

    2009-08-08 22:36:50
    男学生和女学生的联系集:友好程度属性friend,[0,1]之间的。 ; linkmf(students,students)|sex(&1) #eq# 1 #and# sex(&2) #eq# 0: friend; !男学生和女学生的友好程度大于0.5的集; linkmf2(linkmf) | friend...
  • C#微软培训教材(高清PDF)

    千次下载 热门讨论 2009-07-30 08:51:17
    第四章 据 类 型 .28 4.1 值 类 型 .28 4.2 引 用 类 型 .33 4.3 装箱和拆箱 .39 4.4 小 结 .42 第五章 变量和常量 .44 5.1 变 量 .44 5.2 常 量 .46 5.3 小 结 .47 第六章 类 型 转 换 .48 ...
  • 汉堡包和天然气的例子,强调指出了价格的重要性——为单位消费品所付的钱多少,直接影响购物者的抉择。另外,还有其它一些因素也对这种抉择产生影响。我们需要给消费者的需求量和影响需求量的因素之间的关系下一个...
  • C#微软培训资料

    2014-01-22 14:10:17
    <<page 1>> page begin==================== 目 目目 目 录 录录 ... 2000 年 6 月 22 日 不论对 Microsoft 还是对整个 IT 业界将成为值得纪念的一天 这一天 微软公司正式推出了其下一代...
  • 对于交换机来说,任何一种业务要分别在模拟话机、ISDN话机、V5话机、多种形式的话务台上做测试。对于中继的业务,则要充分考虑各种信令:TUP、ISUP、PRA、NO1、V5等等。 【案例1.2.2】 对某交换类进行计费测试,...
  • 千里马酒店前台管理系统V7使用手册

    热门讨论 2011-06-16 14:09:38
    衣带渐宽终不悔,为伊消人憔悴; 众里寻他千百度,蓦然回首,那人却在灯火阑珊处。 欢迎您加入千里马®酒店管理软件的大家庭! 经过近三年的精心研制,全新设计的新一代千里马酒店前台管理系统Pegasus HMS V7.2...
  • [1]表达式计算器用户界面较之按键式计算器简洁多,用户更容易使用。 [2]按键式计算器操作顺序必须由用户自行指定,不具备表达式动态解释执行的特征。[3]按键式计算器运算对象较为简单,难以扩充至矩阵运算。 ...
  • 疯狂的程序员

    热门讨论 2012-07-18 18:05:32
    想我那个年代,这城市有多少程序员,数都出来。我还报了高程,唉……差一点。” 能去教书当然好,因为去教书才有可能从学校里泡个妹妹出来,才有可能和他一样牛B。这么想着,绝影说:“我也想做程序员。” “你...
  • 操作系统(内存管理)

    热门讨论 2009-09-20 12:55:25
    您甚至不必费心思去弄明白它有多少内存,因为每一台机器的内存数量相同。所以,如果内存需要非常固定,那么您只需要选择一个内存范围并使用它即可。 不过,即使是在这样一个简单的计算机中,您也会有问题,尤其...
  • 这样,每个进程获得了自己可以使用的地址空间,可以访问比您物理上安装的内存更多的内存。 在 32-位 x86 系统上,每一个进程可以访问 4 GB 内存。现在,大部分人的系统上并没有 4 GB 内存,即使您将 swap 也...
  • WINRAR5.0正式注册版

    2013-10-10 10:14:03
    32位和64位版本可以解压任何字典大小的压缩文件,包括 1GB的; b) RAR 5.0 的默认字典大小是 32MB,结果就是比 RAR 4.x 的 4MB 更高的压缩率和较 慢的速度。你可以在压缩对话框选择中使用“字典大小”选项或 -...
  • $a - $b : $a * $b :乘 $a / $b :除 $a % $b :取模(余数) $a . $b :字符串连接 逻辑和比较 逻辑运算符有: $a || $b :或 $a or $b :或 $a && $b :与 $a and $b :与 $a xor $b :异或 (当$...
  • 代码语法错误分析工具pclint8.0

    热门讨论 2010-06-29 07:00:09
    选项由类似于操作符和操作的部分组成,例如-esym(534, printf, scanf, operat or new),其中最后一个选项是operator new,那么在operator和new中间只能有一个空 格。 选项还可以放在宏定义中,例如: #...

空空如也

空空如也

1 2
收藏数 32
精华内容 12
关键字:

任何数减0都得任何数