演算法與解題 - 系列文

8: ➫

11: 動態規劃

08: 本節課深入探討分治法的原理及應用，特別是在數據查找問題中的實踐。

分治法簡介
#

分治法的核心是"分而治之"，即將大問題分解為小問題，逐一解決後合併結果。它在計算機科學中應用廣泛，特別是在排序（如快速排序、歸併排序）和數據查找等領域。

分治法的特點
#

問題可分: 大問題可分解為小問題。
問題獨立: 各子問題相互獨立，不互相影響。
解可合併: 子問題解可合併為原問題解。

分治法在數據查找中的應用
#

以二分查找為例，它透過不斷縮小查找範圍來定位元素，展示了分治法在數據查找中的優勢。

二分查找的 Go 實現
#

以下是 Go 語言實現的二分查找算法範例。

func binarySearch(arr []int, target int) int {
    low, high := 0, len(arr)-1
    for low <= high {
        mid := low + (high-low)/2
        if arr[mid] == target {
            return mid
        } else if arr[mid] < target {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
    return -1
}

func main() {
    arr := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
    target := 8
    result := binarySearch(arr, target)
    if result != -1 {
        fmt.Printf("找到數字 %d 在陣列中的位置: %d\n", target, result)
    } else {
        fmt.Println("數字不在陣列中")
    }
}