比較次數，為了直觀一點，如下，第一排為各個數，接下來的5排為查詢對應上面的數的查詢比較次數。1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 2 2 3 3 3 3 4 4 4 4 4 4 4 4 5 5 5 5 5總共比較次數為：1 +2*2 + 4*3 + 8*4+ 5*5 = 74平均長度是 74 /20 =3.7 可以這樣算，二分查詢就是將數列不停的二分一個數列中間只有1個數，比較1次二分後變為2個數列然後查詢這2個數列的中間數，比較次數等於 2個數列 * 2次繼續二分變為4個數列，比較次數變為 4 * 3繼續比較次數為8*4繼續比較次數為16*5，然而，這裡的數只有20個，這裡16顯然多了，20 - 8 - 4 -2 -1 = 5，是5*5 以後你可以按照公式1+2*2 + ...2^(n-1) * n 來算總的比較次數。 log2(n+1)是理想的平均情況，近似值。
比較次數，為了直觀一點，如下，第一排為各個數，接下來的5排為查詢對應上面的數的查詢比較次數。1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 2 2 3 3 3 3 4 4 4 4 4 4 4 4 5 5 5 5 5總共比較次數為：1 +2*2 + 4*3 + 8*4+ 5*5 = 74平均長度是 74 /20 =3.7 可以這樣算，二分查詢就是將數列不停的二分一個數列中間只有1個數，比較1次二分後變為2個數列然後查詢這2個數列的中間數，比較次數等於 2個數列 * 2次繼續二分變為4個數列，比較次數變為 4 * 3繼續比較次數為8*4繼續比較次數為16*5，然而，這裡的數只有20個，這裡16顯然多了，20 - 8 - 4 -2 -1 = 5，是5*5 以後你可以按照公式1+2*2 + ...2^(n-1) * n 來算總的比較次數。 log2(n+1)是理想的平均情況，近似值。