CodeGym /Java Adesua /Python SELF TW /二分搜尋法

二分搜尋法

Python SELF TW

等級 53 , 課堂 1

開放

2.1 定義二分搜尋法及其基本概念

二分搜尋法 是一種在已排序數組中尋找元素的演算法，原理是將數組一分為二。這種演算法比線性搜尋在大數組中更高效，因為它通過在每次迭代中將數組分成兩部分來減少檢查次數。

基本概念：

已排序數組： 二分搜尋法只在已排序的數組上運行。
對半分割： 演算法將搜尋元素與數組中間的元素進行比較。
遞迴或迭代分割： 如果搜尋元素小於中間元素，則在數組左半部繼續搜尋，否則在右半部。
完成條件： 當元素被找到或者搜尋範圍變空時，搜尋結束。

重點！二分搜尋法需要已排序的數組。

為了正確運行二分搜尋法，輸入資料必須按升序排序。這是唯一的要求，因為演算法依賴於數組元素是按順序排列的這一事實。這樣才能在每次搜尋中有效排除一半的元素。

已排序數組示例：


sorted_array = [1, 3, 5, 7, 9, 11, 13]

2.2 二分搜尋法步驟實作

二分搜尋法的工作原理：

初始化： 設置搜尋的初始邊界（數組的左邊界和右邊界）。
選擇中間元素： 找到數組中間元素的索引。
比較： 將中間元素與搜尋值進行比較。
更新邊界：
1. 如果中間元素等於搜尋值，返回其索引。
2. 如果搜尋值小於中間元素，更新右邊界。
3. 如果大於 — 更新左邊界。
重複： 重複步驟2-4直到找到元素或左邊界大於右邊界。

步驟演算法：

初始化： 設置left 為 0 和 right 為 len(arr) - 1。
計算中間元素： mid = (left + right) // 2
與目標元素比較：
1. 如果 arr[mid] == target，返回 mid
2. 如果 arr[mid] < target，更新 left = mid + 1
3. 如果 arr[mid] > target，更新 right = mid - 1
重複： 回到第2步，直到left <= right
如果元素未找到： 返回 -1

Python 中的迭代二分搜尋法實作：


def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# 使用示例：
sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
result = binary_search(sorted_array, target)
print(f"元素 {target} 在索引 {result} 上找到")  # 輸出: 元素 7 在索引 3 上找到

2.3 二分搜尋法的時間複雜度 `O(log n)`

二分搜尋法的時間複雜度是O(log n)，其中n是數組中的元素數量。這意味著在每一步中，演算法將元素數量減半，這大大加速了搜尋速度，相較於時間複雜度為O(n)的線性搜尋。

時間複雜度分析：

最好情況 (Best case): 元素在第一步找到，O(1)。
平均情況 (Average case): O(log n)。
最壞情況 (Worst case): 元素在最後一步找到或不存在，O(log n)。

時間複雜度分析示例：


sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
index = binary_search(sorted_array, target)
print(f"元素 {target} 在索引 {index} 上找到")  # 輸出: 元素 7 在索引 3 上找到

# 演算法已執行 3 步（7 個元素的對數）以找到元素，這符合 O(log n)

複雜度的圖形表示：

想像一下有 16 個元素的數組。