已知一个长度为16的顺序表L,其元素按关键字有序排列。若采用折半查找法查找一个L中不存在的元素,则关键字的比较次数最多的是()。
4
5
6
7
折半查找法在查找成功时进行的关键字比较次数最多为ëlog2nû +1,即判定树的高度;折半查找法在查找不成功时进行的关键字比较次数最多为ëlog2nû +1。题中n=16,因此最多比较ëlog216û +1=5次。也可以画出草图求解。
思考:若本题题干改为求最少的比较次数呢?
比较16之后还要比较一次吧
这道题你会答吗?花几分钟告诉大家答案吧!
扫描二维码,关注牛客网
下载牛客APP,随时随地刷题
折半查找法在查找成功时进行的关键字比较次数最多为ëlog2nû +1,即判定树的高度;折半查找法在查找不成功时进行的关键字比较次数最多为ëlog2nû +1。题中n=16,因此最多比较ëlog216û +1=5次。也可以画出草图求解。
思考:若本题题干改为求最少的比较次数呢?