“Template: 二分查找”的版本间的差异

来自计算思维百科
跳转至: 导航搜索
 
第7行: 第7行:
 
 第一次查找,初始列表中间元素为Harry,按字典排序小于John,新的查找子表为初始列表的后半部分;第二次查找,第一个子表的中间元素为Larry,大于John,在其前半部分查找John;第三次查找,第二个子表的中间元素为John,找到。
 
 第一次查找,初始列表中间元素为Harry,按字典排序小于John,新的查找子表为初始列表的后半部分;第二次查找,第一个子表的中间元素为Larry,大于John,在其前半部分查找John;第三次查找,第二个子表的中间元素为John,找到。
  
 对二分查找,中间元素等于e,找到。但也存在初始列表不含元素e,即找不到的情况 。读者可自行思考此种情况的算法结束条件
+
 对二分查找,中间元素等于e,找到。但也存在初始列表不含元素e,即找不到的情况。

2015年10月24日 (六) 12:43的最新版本

二分查找('Binary Search')是种高效率的查找算法,用于在n个元素的有序序列{ai,i≤i≤n}(假设升序)中查找指定元素e。该算法的思想是:将n个元素分成个数大致相同的两半,取an/2与欲查找的e作比较,如果e=an/2,则找到e,算法终止;如果e<an/2,则只需在数组a的前半部分继续二分查找e;如果x>an/2,则只需在数组a的后半部分继续二分查找e。二分查找每次比较将数据减少一半,也称折半查找。

                           RTENOTITLE

                              图1 二分查找在列表中查找John元素的计算过程
图1给出了二分查找的一个操作实例。假设在初始列表中查找元素John。

第一次查找,初始列表中间元素为Harry,按字典排序小于John,新的查找子表为初始列表的后半部分;第二次查找,第一个子表的中间元素为Larry,大于John,在其前半部分查找John;第三次查找,第二个子表的中间元素为John,找到。

对二分查找,中间元素等于e,找到。但也存在初始列表不含元素e,即找不到的情况。