陣列二分演算法(Array bisection algorithm)

by : R緯

Python官方 bisect

bisect 是 Python 標準庫中的一個模組，主要用於在已排序的序列中進行二分搜尋和插入操作。這個模組提供了幾個函數，可以幫助你快速找到元素的位置，並在保持序列有序的情況下插入新元素。

主要功能

1. 查找位置：

   • bisect.bisect_left(a, x, lo=0, hi=len(a))：返回 x 在序列 a 中應該插入的位置，以保持序列的有序性。如果 x 已經存在，則返回 x 最左邊的位置。
   • bisect.bisect_right(a, x, lo=0, hi=len(a)) 或 bisect.bisect(a, x, lo=0, hi=len(a))：返回 x 在序列 a 中應該插入的位置，以保持序列的有序性。如果 x 已經存在，則返回 x 最右邊的位置。

2. 插入元素：

   • bisect.insort_left(a, x, lo=0, hi=len(a))：在序列 a 中插入 x，保持序列的有序性。如果 x 已經存在，則插入到 x 的左邊。
   • bisect.insort_right(a, x, lo=0, hi=len(a)) 或 bisect.insort(a, x, lo=0, hi=len(a))：在序列 a 中插入 x，保持序列的有序性。如果 x 已經存在，則插入到 x 的右邊。

使用範例

以下是一些使用 bisect 模組的範例：

import bisect

# 已排序的列表
a = [1, 3, 4, 4, 5, 7]

# 查找插入位置
x = 4
pos_left = bisect.bisect_left(a, x)  # 返回 2
pos_right = bisect.bisect_right(a, x)  # 返回 4

print(f"插入 {x} 的左邊位置: {pos_left}")
print(f"插入 {x} 的右邊位置: {pos_right}")

# 插入元素
bisect.insort_left(a, 6)  # 在 5 和 7 之間插入 6
print(a)  # 輸出: [1, 3, 4, 4, 5, 6, 7]

bisect.insort_right(a, 4)  # 在 4 的右邊插入 4
print(a)  # 輸出: [1, 3, 4, 4, 4, 5, 6, 7]

注意事項

• bisect 模組的操作時間複雜度為
  $O(\log (n))$，處理大型數據集非常高效。
• 使用 bisect 模組的前提是序列必須是已排序的，否則結果將不一定正確。

R緯：若x不再序列中???

如果 x 不存在於序列中，bisect.insort_left 和 bisect.insort_right 的行為如下：

1. bisect.insort_left(a, x, lo=0, hi=len(a))：

   • 這個函數會在序列 a 中找到 x 應該插入的位置，並將 x 插入到該位置。由於 insort_left 是基於 bisect_left 的，因此它會將 x 插入到 x 應該出現的最左邊位置。
   • 如果 x 不存在於序列中，insort_left 會將 x 插入到它應該出現的位置，這樣序列仍然保持有序。

2. bisect.insort_right(a, x, lo=0, hi=len(a)) 或 bisect.insort(a, x, lo=0, hi=len(a))：

   • 這個函數會在序列 a 中找到 x 應該插入的位置，並將 x 插入到該位置。由於 insort_right 是基於 bisect_right 的，因此它會將 x 插入到 x 應該出現的最右邊位置。
   • 如果 x 不存在於序列中，insort_right 會將 x 插入到它應該出現的位置，這樣序列仍然保持有序。

總結

• 如果 x 存在於序列中：

  • insort_left 將 x 插入到最左邊的位置。
  • insort_right 將 x 插入到最右邊的位置。

• 如果 x 不存在於序列中：

  • 兩者都會將 x 插入到它應該出現的位置，保持序列的有序性。

示例

假設有一個序列：

a = [1, 3, 4, 5, 7]

• 使用 insort_left 插入 2：

import bisect

bisect.insort_left(a, 2)
print(a)  # 輸出: [1, 2, 3, 4, 5, 7]

• 使用 insort_right 插入 6：

bisect.insort_right(a, 6)
print(a)  # 輸出: [1, 2, 3, 4, 5, 6, 7]

在這些情況下，無論 x 是否存在於序列中，插入操作都能保持序列的有序性。

參數lo & hi

在 bisect 模組中，lo 和 hi 參數用於指定要考慮的序列範圍。這些參數可以幫助你在序列的特定部分進行插入操作，而不是整個序列。以下是這兩個參數的詳細說明：

在 bisect 模組中，lo 和 hi 參數的全稱分別是：

• lo: lower bound（下界）
• hi: higher bound（上界）

這兩個參數用於指定在序列中進行搜尋和插入操作的範圍。具體來說：

• lo（下界）指定了搜尋的起始索引，表示從這個索引開始考慮序列的元素。
• hi（上界）指定了搜尋的結束索引，表示到這個索引之前的元素（不包括 hi 本身）。

這樣的設計使得你可以在序列的特定部分進行操作，而不必對整個序列進行搜尋，從而提高效率。

參數說明

1. lo：

   • 這個參數指定了要開始搜尋的索引位置。默認值是 0，表示從序列的開頭開始搜尋。
   • 如果你想要在序列的某個特定部分進行插入，可以設置 lo 為該部分的起始索引。

2. hi：

   • 這個參數指定了要結束搜尋的索引位置。默認值是 len(a)，表示到序列的結尾。
   • 如果你只想在序列的某個特定部分進行插入，可以設置 hi 為該部分的結束索引。

使用範例

假設有一個序列：

a = [1, 3, 4, 5, 7]

使用 lo 和 hi 參數

1. 插入到特定範圍：

import bisect

# 在索引 1 到 4 的範圍內插入 4
bisect.insort_left(a, 4, lo=1, hi=4)
print(a)  # 輸出: [1, 3, 4, 4, 5, 7]

在這個例子中，insort_left 只考慮了索引 1 到 4 的範圍（即 [3, 4, 5]），因此它將 4 插入到最左邊的位置。

2. 插入到特定範圍的右邊：

# 在索引 0 到 3 的範圍內插入 4
bisect.insort_right(a, 4, lo=0, hi=3)
print(a)  # 輸出: [1, 3, 4, 4, 4, 5, 7]

在這個例子中，insort_right 只考慮了索引 0 到 3 的範圍（即 [1, 3, 4]），因此它將 4 插入到最右邊的位置。

總結

• lo 和 hi 參數允許你在序列的特定部分進行插入操作，這在處理大型數據集或需要對特定範圍進行操作時非常有用。
• 通過設置這些參數，你可以控制插入操作的範圍，從而提高效率或滿足特定需求。

R緯：如果序列無序會Error嗎???

如果序列 a 是無序的，使用 bisect 模組的函數（如 bisect_left、bisect_right、insort_left 和 insort_right）將不會產生正確的結果。這是因為 bisect 模組的設計是基於已排序的序列進行二分搜尋和插入操作的。

具體情況

1. 查找位置：

   • 如果你在無序序列中使用 bisect.bisect_left(a, x) 或 bisect.bisect_right(a, x)，返回的索引可能不正確，因為這些函數假設序列是有序的。它們會根據序列的當前排列進行搜尋，這可能導致錯誤的插入位置。

2. 插入元素：

   • 使用 bisect.insort_left(a, x) 或 bisect.insort_right(a, x) 在無序序列中插入元素也會導致序列不再有序。這是因為這些函數會根據無序序列的當前狀態插入元素，而不會考慮最終的有序性。

示例

假設有一個無序的序列：

a = [3, 1, 4, 5, 2]

如果你嘗試使用 bisect 函數：

import bisect

# 嘗試查找 4 的位置
pos_left = bisect.bisect_left(a, 4)  # 返回的可能是 2，但這不正確
pos_right = bisect.bisect_right(a, 4)  # 返回的可能是 3，但這也不正確

print(f"pos_left: {pos_left}, pos_right: {pos_right}")

這裡的 pos_left 和 pos_right 返回的索引可能不正確，因為 a 是無序的。

總結

• bisect 模組的函數假設序列是已排序的，因此在無序序列中使用這些函數會導致不正確的結果。
• 如果你需要在無序序列中進行插入或查找操作，建議先對序列進行排序，然後再使用 bisect 模組的功能。你可以使用 sorted() 函數或 list.sort() 方法來對序列進行排序。

R緯：bisect 函式完整流程

bisect 模組的函數主要用於在已排序的序列中進行查找和插入操作。以下是 bisect 模組中主要函數的完整過程，包括 bisect_left、bisect_right、insort_left 和 insort_right 的詳細步驟。

1. bisect.bisect_left(a, x, lo=0, hi=len(a))

目的

查找 x 在序列 a 中應該插入的位置，以保持序列的有序性。如果 x 已經存在，則返回 x 最左邊的位置。

完整過程

1. 初始化：

   • 設定 low 為 lo，high 為 hi。

2. 二分搜尋：

   • 當 low 小於或等於 high 時，執行以下步驟：
     1. 計算中間位置：mid = (low + high) // 2。
     2. 比較：
        • 如果 a[mid] < x，則更新 low = mid + 1（在右半部分繼續搜尋）。
        • 如果 a[mid] >= x，則更新 high = mid（在左半部分繼續搜尋）。

3. 返回結果：

   • 當 low 等於 high 時，返回 low，這就是 x 應該插入的位置。

2. bisect.bisect_right(a, x, lo=0, hi=len(a))

目的

查找 x 在序列 a 中應該插入的位置，以保持序列的有序性。如果 x 已經存在，則返回 x 最右邊的位置的下一個位置。

完整過程

1. 初始化：

   • 設定 low 為 lo，high 為 hi。

2. 二分搜尋：

   • 當 low 小於或等於 high 時，執行以下步驟：
     1. 計算中間位置：mid = (low + high) // 2。
     2. 比較：
        • 如果 a[mid] <= x，則更新 low = mid + 1（在右半部分繼續搜尋）。
        • 如果 a[mid] > x，則更新 high = mid（在左半部分繼續搜尋）。

3. 返回結果：

   • 當 low 等於 high 時，返回 low，這就是 x 應該插入的位置。

3. bisect.insort_left(a, x, lo=0, hi=len(a))

目的

在序列 a 中插入 x，保持序列的有序性。如果 x 已經存在，則插入到 x 的左邊。

完整過程

1. 查找插入位置：

   • 使用 bisect_left 查找 x 應該插入的位置。

2. 插入元素：

   • 在該位置使用 list.insert() 方法插入 x。

4. bisect.insort_right(a, x, lo=0, hi=len(a))

目的

在序列 a 中插入 x，保持序列的有序性。如果 x 已經存在，則插入到 x 的右邊。

完整過程

1. 查找插入位置：

   • 使用 bisect_right 查找 x 應該插入的位置。

2. 插入元素：

   • 在該位置使用 list.insert() 方法插入 x。

證明 bisect 模組的操作時間複雜度為

$O(\log (n))$

bisect 模組的操作時間複雜度為

$O(\log (n))$ 的證明主要基於二分搜尋算法的特性。以下是對這一點的詳細解釋：

二分搜尋的基本原理

二分搜尋是一種高效的搜尋算法，適用於已排序的數據結構。其基本步驟如下：

1. 初始化：設置兩個指標，low 和 high，分別指向序列的開始和結束。
2. 計算中間位置：計算中間位置 mid，通常使用公式 mid = (low + high) // 2。
3. 比較：
   • 如果中間元素等於目標值，則找到目標，返回該位置。
   • 如果中間元素小於目標值，則目標值必定在右半部分，更新 low 為 mid + 1。
   • 如果中間元素大於目標值，則目標值必定在左半部分，更新 high 為 mid - 1。
4. 重複：重複上述步驟，直到找到目標值或 low 超過 high。

時間複雜度分析

在每次迭代中，二分搜尋將搜索範圍減半。這意味著：

• 第一次搜尋範圍是
  $n$（整個序列）。
• 第二次搜尋範圍是
  $\frac{n}{2}$。
• 第三次搜尋範圍是
  $\frac{n}{4}$。
• 依此類推。

因此，搜尋的步驟數量可以表示為：

$$n,\frac{n}{2},\frac{n}{4},\frac{n}{8},\dots$$

這樣的序列會在

$k$ 步驟後達到 1，滿足以下不等式：

$$\frac{n}{2^k}\le 1$$

解這個不等式，我們可以得到：

$$n\le 2^k⟹k\ge {\log }_2(n)$$

因此，二分搜尋的最壞情況下的時間複雜度為

$O(\log (n))$。

結論

由於 bisect 模組的 bisect_left 和 bisect_right 函數都是基於二分搜尋算法實現的，因此它們的時間複雜度也是

$O(\log (n))$。這使得在已排序的序列中查找插入位置的操作非常高效。

R緯：

${\log }_2(n)$ 為什麼可以表示為

$O(\log (n))$

這是因為不同的對數底數之間存在著常數倍的關係。具體來說:

$${\log }_a(n)=\frac{{\log }_b(n)}{{\log }_b(n)}$$

其中

$a$ 和

$b$ 是任意的正實數底數。
根據上式,我們可以得到:

$${\log }_2(n)=\frac{\ln (n)}{\ln (2)}=\frac{1}{\ln (2)}\ln (n)$$

備註：

$\ln (n)$ 就是自然對數

${\log }_e(n)$。

由於

$\frac{1}{\ln (2)}$ 是一個常數,因此

$${\log }_2(n)=O(\ln (n))=O(\log (n))$$

也就是說,不管我們使用以 2 為底還是以自然對數為底,時間複雜度都是

$O(\log (n))$。因為它們之間只相差一個常數因子。

因此,我們可以說 bisect 模組中的所有函數都有

$O(\log (n))$ 的時間複雜度,不管是使用

${\log }_2(n)$ 還是其他對數形式來表示。關鍵在於它們都遵循二分搜尋的原理,這決定了它們的時間複雜度為對數等級。