點(diǎn)擊查看：2015年計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)復(fù)習(xí)知識(shí)點(diǎn)匯總

　　二分法查找

　　二分查找只適用于順序存儲(chǔ)的有序表。此處所述的有序表是指線性中的元素按值非遞減排列(即由小到大，但允許相鄰元素值相等)。

　　二分查找的方法如下：

　　將要查找的元素與有序序列的中間元素進(jìn)行比較：

　　如果該元素比中間元素大，則繼續(xù)在線性表的后半部分(中間項(xiàng)以后的部分)進(jìn)行查找

　　如果要查找的元素的值比中間元素的值小，則繼續(xù)在線性表的前半部分(中間項(xiàng)以前的部分)進(jìn)行查找

　　這個(gè)查找過程一直按相同的順序進(jìn)行下去，一直到查找成功或子表長(zhǎng)度為0(說明線性表中沒有要查找的元素)

　　有序線性表的二分法查找，條件是必須這個(gè)有序線性表的存儲(chǔ)方式是順序存儲(chǔ)的。它的查找效率比順序查找要高得多，它的最壞情況的查找次數(shù)是log2n次，而順序查找的最壞情況的查找次數(shù)是n次。

　　當(dāng)然，二分查找的方法也支持順序存儲(chǔ)的遞減序列的線性表。

　　有非遞減有序線性表：1、2、4、5、7、9，要查找元素6。查找的方法是：

　　序列長(zhǎng)度為n=6，中間元素的序號(hào)m=[(n+1)/2]=3

　　查找計(jì)次k=1，將元素6與中間元素即元素4進(jìn)行比較，不等，6>4

　　查找計(jì)次k=2，查找繼續(xù)在后半部分進(jìn)行，后半部分子表的長(zhǎng)度為3，計(jì)算中間元素的序號(hào)：m=3+[(3+1)/2]=5，將元素與后半部分的中間項(xiàng)進(jìn)行比較，即第5個(gè)元素中的7進(jìn)行比較，不等，6<7

　　查找計(jì)次k=3，繼續(xù)查找在后半部分序列的前半部分子序列中查找，子表長(zhǎng)度為1，則中間項(xiàng)序號(hào)即為m=3+[(1+1)/2]=4，即與第4個(gè)元素5進(jìn)行比較，不相等，繼續(xù)查找的子表長(zhǎng)度為0，則查找結(jié)束

　　相關(guān)推薦：

　　2015年9月計(jì)算機(jī)等級(jí)考試成績(jī)查詢時(shí)間通知

　　2015計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)精選選擇題專項(xiàng)練習(xí)

　　2015計(jì)算機(jī)二級(jí)《公共基礎(chǔ)知識(shí)》精選選擇題90道