二分查找
又称为折半查找（Binary Search）
它要求线性表中结点必须按关键字值递增或递减顺序排列
二分查找的基本思想首先用要查找的关键字K与中间位置的结点的关键字相比较这个中间结点把线性表分成了两个子表若比较结果相等则查找完成若不相等再根据K与该中间结点关键字的比较大小确定下一步查找哪个子表这样递归下去直到找到满足条件的结点或者该线性表中没有这样的结点
二分查找示例
在等概率假设下二分查找成功时的平均查找长度近似于lg(n+)在查找失败时所需比较的关键字个数不超过判定树的深度在最坏情况下查找成功的比较次数也不超过判定树的深度┌lg(n+)┐
二分查找只适用于顺序存储结构
