二分查找：

二分查找又稱折半查找，優(yōu)點是比較次數(shù)少，查找速度快，平均性能好；其缺點是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用于不經(jīng)常變動而查找頻繁的有序列表。
??原理：假設表中元素是按升序排列，將表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成左、右(左邊小一些)兩個子表，如果中間位置記錄的關鍵字大于查找關鍵字，則進一步查找左子表，否則進一步查找右子表。重復以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。

特征：1）序列有序；2）可以隨機訪問
爭議：表必須有序，表可以順序方式存儲，也可以鏈表方式存儲。有人說，表只能順序存儲；但也有人說，折半查找也可以用跳表實現(xiàn)，跳表即不是順序存儲。跳表維基百科

時間復雜度: O(log₂N)

我們首先來看一下實現(xiàn)代碼：
非遞歸方式

int BinarySearch(const ElementType A[ ], ElementType X, int N) {int Low, Mid, High;Low = 0; High = N - 1;while( Low <= High ){Mid = ( Low + High ) / 2;if( A[Mid] < X )Low = Mid + 1;elseif( A[Mid] > X )High = Mid - 1;elsereturn Mid; /* Found */}return NotFound; /* NotFound is defined as -1 */ }

時間復雜度分析T_worst(N)

顯然，每次迭代在循環(huán)內(nèi)的所有工作花費為O(1)。
二分查找每次排除掉一半的不適合值，所以對于N個元素的情況：

一次二分剩下：N/2
兩次二分剩下：N/2/2 = N/4
…
M次二分剩下：N/(2^M)

在最壞情況下是在排除到只剩下最后一個值之后得到結果，即

N/(2^M)=1

所以由上式可得 ： 2^M=N $?$ T(N) = log₂(N)

遞歸方式

int BinarySearchRecursion(const ElementType A[ ], ElementType X, int Start, int End) { /* 1 */ if( Start > End )return NotFound; /* NotFound is defined as -1 *//* 2 */ int Mid = ( Start + End ) / 2; /* 3 */ if(X == A[Mid])return Mid; /* Found */elseif(X < A[Mid]) /* 4 */ BinarySearchRecursion(A, X, Start, Mid - 1);else if(X > A[Mid]) /* 5 */ BinarySearchRecursion(A, X, Mid + 1, End); }

令T(N)是求解大小為N的二分法排序問題所花費的時間。如果N = 1，則上面算法執(zhí)行程序第1行到第3行，花費某個時間常量，我們稱之為一個時間單元.于是，T(1) = 1。其余就是第4行，第5行上的運行工作。這兩行求解大小為N/2的二分法排序問題。假設N為偶數(shù)，因此這兩行花費之和**總是T(N/2)**個時間單位，于是我們得到方程組:
$$\{\begin{array}{l}T(1)=1\\ T(N)=T(N/2)+O(1)\end{array}$$
為了簡化計算，我們可以用1代替上面方程中的O(1)項；由于T(N)最終還是要用大O來喪示的，因此這么做并不影響答案。
至于現(xiàn)在，T(N) = T(N/2) + 1，且T(1) = 1，那么T(2) = 1+1，T(4) = 2+1，T(8) = 3+1，T(16) = 4+1。
其形式是顯然的并且可以得到T(N) = log₂N + 1 = O(log₂N)

附：
算法時間復雜度比較圖

《數(shù)據(jù)結構與算法分析》-----Mark Allen Weiss
二分查找時間復雜度計算與分析

總結

以上是生活随笔為你收集整理的二分查找与时间复杂度计算分析的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。