数据结构查找和排序.ppt

第一部分 查找 二分查找,Hash表 二分查找考点 条件顺序存储,按关键字有序 时间复杂度分析log2n 最多要比较的次数?2n? +1 ,理由n个结点的判定树的深度与n个结点的完全二叉树深度相同 折半查找的二叉判定树 1请问,满足什么条件的顺序表可以实施二分查找,在满足该条件的n个记录的顺序表中进行二分查找,最大的比较次数是多少 答数据元素初始状态按关键字有序 最大比较次数应为?2n? +1