二分法查找
對序列進行遞歸的查找演演算法
演演算法：二分法查找適用於數據量較大時，但是數據需要先排好順序。主要思想是：（設查找的數組區間為array[low, high]）
（1）確定該區間的中間位置K（2）將查找的值T與array[k]比較。若相等，查找成功返回此位置；否則確定新的查找區域，繼續二分查找。區域確定如下：a.array[k]>T 由數組的有序性可知array[k,k+1,……,high]>T;故新的區間為array[low,……，K-1]b.array[k]
假如有一組數為3，12，24，36，55，68，75，88要查給定的值24.可設三個變數front，mid，end分別指向數據的上界，中間和下界，mid=（front+end）/2.
1.開始令front=0（指向3），end=7（指向88），則mid=3（指向36）。因為a[mid]>x，故應在前半段中查找。
2.令新的end=mid-1=2，而front=0不變，則新的mid=1。此時x>a[mid]，故確定應在後半段中查找。
3.令新的front=mid+1=2，而end=2不變，則新的mid=2，此時a[mid]=x，查找成功。
如果要查找的數不是數列中的數，例如x=25，當第三次判斷時，x>a[mid]，按以上規律，令front=mid+1，即front=3，出現front>end的情況，表示查找不成功。
例：在有序的有N個元素的數組中查找用戶輸進去的數據x。
演演算法如下：
1.確定查找範圍front=0，end=N-1，計算中項mid=（front+end）/2。
2.若a[mid]=x或front>=end,則結束查找；否則，向下繼續。
3.若a[mid]x，說明待查找的元素值只可能在比中項元素小的範圍內，則把mid-1的值賦給end，並重新計算mid，轉去執行步驟2。
1.最壞情況查找最後一個元素（或者第一個元素）Master定理T(n)=T(n/2)+O(1)所以T(n)=O(log2n)
2.最好情況查找中間元素O(1)查找的元素即為中間元素（奇數長度數列的正中間，偶數長度數列的中間靠左的元素）
S(n)=n
1.
S(n)=n
基本信息
- 中文名
- 二分法查找
- 外文名
- Binary Search
- 類型
- 查找演算法
- 主要思想
- 對序列進行遞歸（或循環查找）
- 要求
- 數據需是排好序的