HW#00 python基礎

1.notebook

2.

3.學習卡，測驗

4.

Python 實作的二元搜尋演算法（Binary Search）程式碼。這是一種在「已排序陣列」中尋找特定元素的高效演算法。

Python 程式碼實作

python

def binary_search(arr, target):
    """
    在已排序的陣列 arr 中尋找 target 的索引位置。
    如果找到，傳回該元素的索引；若未找到，傳回 -1。
    """
    low = 0
    high = len(arr) - 1

    while low <= high:
        # 計算中間索引，使用 // 進行整除
        mid = (low + high) // 2
        guess = arr[mid]

        # 檢查是否找到目標值
        if guess == target:
            return mid
        # 如果猜的數字太大，調整右邊界
        elif guess > target:
            high = mid - 1
        # 如果猜的數字太小，調整左邊界
        else:
            low = mid + 1

    # 若搜尋範圍耗盡仍未找到目標值，傳回 -1
    return -1

# 測試程式碼
if __name__ == "__main__":
    # 必須是已排序的陣列
    my_list = [1, 3, 5, 7, 9, 11, 13, 15]
    target_value = 7
    
    result = binary_search(my_list, target_value)
    
    if result != -1:
        print(f"目標元素 {target_value} 位於索引位置：{result}")
    else:
        print(f"陣列中找不到目標元素 {target_value}")

請謹慎使用程式碼。

---

程式碼核心原理解釋

二元搜尋採用了分治法（Divide and Conquer）的思想，每次將搜尋範圍縮減一半：

1. 初始化邊界：設定兩個指標 low（最左端索引 0）與 high（最右端索引 len(arr) - 1）。
2. 尋找中間點：在 while 迴圈中，計算中間索引 mid = (low + high) // 2，並取出該位置的值 guess。
3. 條件判斷與縮小範圍：
   • 剛好猜中 (guess == target)：直接傳回目前的索引 mid。
   • 猜得太大 (guess > target)：代表目標值在左半邊，因此將右邊界縮小為 high = mid - 1。
   • 猜得太小 (guess < target)：代表目標值在右半邊，因此將左邊界擴大為 low = mid + 1。
4. 結束條件：當 low > high 時，代表整個陣列都檢查過了卻沒有匹配的項目，迴圈結束並傳回 -1。

效能分析

• 時間複雜度：\(O(\log n)\)。例如在 1,000 個元素的陣列中，最多只需要檢查約 10 次（2¹⁰ ≈ 1024）。
• 空間複雜度：O(1)。此方法僅使用固定數量的變量（low, high, mid, guess），不需要額外的記憶體空間。

5