山东军队文职招聘考试网计算机常识-二分法查找 - 常识判断

山东军队文职招聘考试网计算机常识-二分法查找减小字体增大字体山东军队文职招聘考试网计算机常识-二分法查找

二分法查找只适用于存储的有序表。在此所说的有序表是指线性表的中元素按值非递减排列(即从小到大,但允许相邻元素值相等)。

设有序线性表的长度为n,被查元素为x,则对分查找的方法如下:

将x与线性表的中间项进行比较:

若中间项的值等于x,则说明查到,查找结束;

若x小于中间项的值,则在线性表的前半部分(即中间项以前的部分)以相同的方法进行查找;

若x大于中间项的值,则在线性表的后半部分(即中间项以后的部分)以相同的方法进行查找。

这个过程一直进行到查找成功或子表长度为0(说明线性表中没有这个元素)为止。

显然,当有序线性表为顺序存储时才能采用二分查找,并且,二分查找的效率要比顺序查找高得多。可以证明,对于长度为n的有序线性表,在最坏情况下,二分查找只需要比较log2n次,而顺序查找需要比较n次。

用户名:!查看更多评论

分值:100分55分1分

内容:!

通知管理员验证码:点击获取验证码