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