山東軍隊(duì)文職招聘考試網(wǎng)計(jì)算機(jī)常識(shí)-二分法查找 - 常識(shí)判斷
山東軍隊(duì)文職招聘考試網(wǎng)計(jì)算機(jī)常識(shí)-二分法查找減小字體增大字體山東軍隊(duì)文職招聘考試網(wǎng)計(jì)算機(jī)常識(shí)-二分法查找
二分法查找只適用于存儲(chǔ)的有序表。在此所說的有序表是指線性表的中元素按值非遞減排列（即從小到大，但允許相鄰元素值相等）。
設(shè)有序線性表的長(zhǎng)度為n，被查元素為x，則對(duì)分查找的方法如下：
將x與線性表的中間項(xiàng)進(jìn)行比較：
若中間項(xiàng)的值等于x，則說明查到，查找結(jié)束；
若x小于中間項(xiàng)的值，則在線性表的前半部分（即中間項(xiàng)以前的部分）以相同的方法進(jìn)行查找；
若x大于中間項(xiàng)的值，則在線性表的后半部分（即中間項(xiàng)以后的部分）以相同的方法進(jìn)行查找。
這個(gè)過程一直進(jìn)行到查找成功或子表長(zhǎng)度為0（說明線性表中沒有這個(gè)元素）為止。
顯然，當(dāng)有序線性表為順序存儲(chǔ)時(shí)才能采用二分查找，并且，二分查找的效率要比順序查找高得多。可以證明，對(duì)于長(zhǎng)度為n的有序線性表，在最壞情況下，二分查找只需要比較log2n次，而順序查找需要比較n次。
用戶名：！查看更多評(píng)論
分值：100分55分1分
內(nèi)容：！
通知管理員驗(yàn)證碼：點(diǎn)擊獲取驗(yàn)證碼
