在實際開發中會遇到一些工程問題，需要求解復雜函數方程的問題。使用傳統的數學方法比較難以處理。本文將使用二分法不斷獲取一個函數的近似解。

二分法：其基本思想是利用函數在某個區間內的連續性，通過不斷縮小區間范圍來逼近方程的解。

算法前置要求

在使用二分法求解函數值近似解之前，需要滿足以下幾個前置條件：

• 函數連續性
  為了確保在區間內存在一個近似解，函數 f(x)必須是連續的。否則，可能會因為函數不連續導致二分法無法收斂到正確的解。

• 單調性判斷
  在應用時需要確保函數在所選區間內為單調函數。二分法在求解過程中的邊界更新依賴于函數的單調性判斷。通過比較區間端點的函數值來決定是否為單調遞增或者遞減。 如果函數整體不是單調的，但是在某區間內單調遞增或者單調遞減，那么也可以求區間內的結果。

• 初始區間覆蓋目標值
  要求區間 [lowerBound,upperBound]的值域內必須包含目標值 target 的對應函數值。

以函數示例 f(x) = x^3 - 4x^2 + 6x - 24，同時滿足3個條件：? ?連續性 && 單調性 && 起始位置覆蓋區間值

算法思路

整個算法的核心步驟如下：

1. 區間初始化
   首先，在已知的區間 [lowerBound,upperBound]內，假設函數 f(x)在此區間內是單調連續的，并且存在滿足條件的解。

2. 迭代過程

   • 計算當前區間的中點 mid。
   • 判斷當前區間長度是否小于 x 方向的容忍誤差 toleranceX，如果滿足條件，則停止迭代。
   • 同時，計算 f(mid)?與目標值 target 的差距，如果差距小于函數值的容忍誤差 toleranceResult，則認為找到近似解。
   • 判斷函數的單調性
     • 單調遞增函數：如果 f(mid)小于 target，則將lowerBound更新為 mid；如果f(mid)大于 target，?則將upperBound更新為 mid。
     • 單調遞減函：如果 f(mid)大于 target，則將lowerBound更新為 mid；如果f(mid)小于 target，?則將upperBound更新為 mid。

3. 結果判斷
   當迭代結束后，比較區間兩端點以及中點的函數值誤差，選擇誤差最小的點作為最終結果返回。

代碼實現與詳細注釋

下面是 Swift 語言實現的完整代碼，函數 f(x) 可以替換成其他單調連續函數：

import Foundationclass YCCloseToResult: NSObject {// 定義函數 f(x) = x^3 - 4x^2 + 6x - 24static func f(x: Double) -> Double {return pow(x, 3) - 4 * pow(x, 2) + 6 * x - 24}// 二分法：在區間 [lowerBound, upperBound] 內尋找使得 f(x) 接近 target 的 x 值/// - Parameters:///   - target: 目標函數值，即希望 f(x) 接近的數值。///   - lowerBound: 搜索區間的下界，表示在該值以上開始尋找滿足條件的 x 值。///   - upperBound: 搜索區間的上界，表示在該值以下開始尋找滿足條件的 x 值。///   - toleranceX: x 方向的容忍誤差。當上下界之差小于此值時，認為 x 的精度已經滿足要求，從而停止迭代。///   - toleranceResult: 函數值的容忍誤差。當 f(x) 與 target 的差值小于此值時，認為已經找到了足夠精確的近似解，從而停止迭代。/// - Returns: 返回使 f(x) 接近 target 的 x 值；如果在給定區間內沒有找到合適的解，則返回 nil。static func bisectionMethod(target: Double, lowerBound: Double, upperBound: Double, toleranceX: Double = 0.01, toleranceResult: Double = 0.01) -> Double? {var lower = lowerBound   // 區間下界var upper = upperBound   // 區間上界var mid: Double = 0var loopCount = 0        // 記錄循環次數var fMid: Double = 0     // 中點對應的 f(x) 值var fUpper: Double = self.f(x: upper)   // 上界對應的 f(x) 值var fLower: Double = self.f(x: lower)   // 下界對應的 f(x) 值if target > max(fLower, fUpper) || target < min(fLower, fUpper) {print("目標值不在給定區間內")return nil}// 開始迭代while true {loopCount += 1mid = (lower + upper) / 2  // 計算中點// 如果區間長度小于 x 的容忍誤差，則認為 x 精度達到要求if (upper - lower) <= toleranceX {print("x誤差達到精度要求")break}// 計算當前下界、中點和上界的函數值fMid = self.f(x: mid)fUpper = self.f(x: upper)fLower = self.f(x: lower)print("循環次數: \(loopCount); f(\(lower))=\(fLower), f(\(mid))=\(fMid), f(\(upper))=\(fUpper)")// 如果中點對應的函數值與目標值之間的誤差滿足要求，則退出循環if abs(fMid - target) < toleranceResult {print("結果達到精度要求")break} else {// 根據函數單調性判斷：這里假設函數在區間內單調if fLower < fUpper {  // 單調遞增函數// 如果中點的函數值小于目標值，則更新下界if fMid < target {lower = mid} else { // 否則更新上界upper = mid}} else {  // 單調遞減函數if fMid < target {upper = mid} else {lower = mid}}}}print("總循環次數: \(loopCount)")// 在 lower, mid, upper 中選擇哪個點的函數值最接近 targetlet absLower = abs(fLower - target)let absMid = abs(fMid - target)let absUpper = abs(fUpper - target)var result: Double = 0if absLower < absMid, absLower < absUpper {result = lower} else if absMid < absLower, absMid < absUpper {result = mid} else {result = upper}return result}
}// 測試函數
extension YCCloseToResult {// 示例入口函數，用于測試二分法查找static func test() {// 目標函數值let target = 10.13// x 的容忍誤差：當上下界的差值小于這個值時停止迭代let toleranceX: Double = 0.01// 函數值的容忍誤差：當 f(x) 與 target 的差值小于這個值時認為已找到近似解let toleranceResult: Double = 0.001// 調用二分法函數，尋找使 f(x) 接近 target 的 x 值if let result = self.bisectionMethod(target: target, lowerBound: -100, upperBound: 100, toleranceX: toleranceX, toleranceResult: toleranceResult) {print("\(target) 的近似解是 \(result)")// 分別打印 result 左側、處于和右側附近的 x 對應的函數信息self.showInfo(result: result-toleranceX, target: target)self.showInfo(result: result, target: target)self.showInfo(result: result+toleranceX, target: target)} else {print("在給定的范圍內沒有找到解。")}}// 打印函數 f(x) 的值以及與目標值 target 的誤差static func showInfo(result: Double, target: Double) {let fRes = self.f(x: result)let absRes = abs(fRes - target)print("f(\(result)) 的值是 \(fRes), 誤差為 \(absRes)")}
}

運行結果： 通過不斷的二分接近，最終求得結果

10.13 的近似解是 4.401206970214844

f(4.401206970214844) 的值是 10.178870703912295, 和目標差值為 0.048870703912294644

二分查找的時間復雜度為O(logN)，效率還不錯。

使用Python畫的函數圖。

import matplotlib.pyplot as plt
import numpy as np# 定義函數 f(x)
def f(x):return x**3 - 4*x**2 + 6*x - 24# 生成 x 值
x = np.linspace(-10000, 10000, 10)
# 計算對應的 y 值
y = f(x)# 創建圖形
plt.figure(figsize=(10, 6))
plt.plot(x, y, label=r'$f(x) = x^3 - 4x^2 + 6x - 24$')# 添加標題和標簽
plt.title('Plot of $f(x) = x^3 - 4x^2 + 6x - 24$')
plt.xlabel('x')
plt.ylabel('f(x)')# 添加網格
plt.grid(True)# 顯示圖例
plt.legend()# 顯示圖形
plt.show()