山東公務員考試網計算機常識-二分法查找

二分法查找只適用于存儲的有序表。在此所說的有序表是指線性表的中元素按值非遞減排列（即從小到大，但允許相鄰元素值相等）。

設有序線性表的長度為n，被查元素為x，則對分查找的方法如下：

將x與線性表的中間項進行比較：

若中間項的值等于x，則說明查到，查找結束；

若x小于中間項的值，則在線性表的前半部分（即中間項以前的部分）以相同的方法進行查找；

若x大于中間項的值，則在線性表的后半部分（即中間項以后的部分）以相同的方法進行查找。

這個過程一直進行到查找成功或子表長度為0（說明線性表中沒有這個元素）為止。

顯然，當有序線性表為順序存儲時才能采用二分查找，并且，二分查找的效率要比順序查找高得多。可以證明，對于長度為n的有序線性表，在最壞情況下，二分查找只需要比較log2n次，而順序查找需要比較n次。

更多精彩資訊請關注查字典資訊網，我們將持續為您更新最新資訊!