Template: 二分查找

来自计算思维百科
Weapon讨论 | 贡献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,即找不到的情况。