點擊查看：2015年計算機二級公共基礎知識復習知識點匯總

　　二分法查找

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

　　二分查找的方法如下：

　　將要查找的元素與有序序列的中間元素進行比較：

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

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

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

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

　　當然，二分查找的方法也支持順序存儲的遞減序列的線性表。

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

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

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

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

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

　　相關推薦：

　　2015年9月計算機等級考試成績查詢時間通知

　　2015計算機二級公共基礎知識精選選擇題專項練習

　　2015計算機二級《公共基礎知識》精選選擇題90道