二分法查找

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

二分查找的方法如下：

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

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

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

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

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

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

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

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

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

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

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

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