二分法檢視原始碼討論檢視歷史
| 二分法 |
對於區間[a，b]上連續不斷且f（a）·f（b）<0的函數y=f（x），通過不斷地把函數f（x）的零點所在的區間一分為二，使區間的兩個端點逐步逼近零點，進而得到零點近似值的方法叫二分法。
簡介
算法：當數據量很大適宜採用該方法。採用二分法查找時，數據需是排好序的。基本思想：假設數據是按升序排序的，對於給定值x，從序列的中間位置開始比較，如果當前位置值等於x，則查找成功；若x小於當前位置值，則在數列的前半段中查找；若x大於當前位置值則在數列的後半段中繼續查找，直到找到為止。假如有一組數為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）。因為mid>x，故應在前半段中查找。2.令新的end=mid-1=2，而front=0不變，則新的mid=1。此時x>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。
評價
若a[mid]<x,說明待查找的元素值只可能在比中項元素大的範圍內，則把mid+1的值賦給front，並重新計算mid，轉去執行步驟2；若a[mid]>x，說明待查找的元素值只可能在比中項元素小的範圍內，則把mid-1的值賦給end，並重新計算mid，轉去執行步驟2。end;//本段程序中stone是要排序的數組，從小到大排序，stone數組為longint（長整型）類型。在主程序中的調用命令為「work(1,n);」不含引號。表示將stone數組中的1到n號元素進行排序。[1]