# 陣列二分演算法(Array bisection algorithm)
by : R緯
## [Python官方 bisect](https://docs.python.org/zh-tw/3.10/library/bisect.html#bisect.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}, \ldots$$

這樣的序列會在 $k$ 步驟後達到 1，滿足以下不等式：

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

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

$$n \leq 2^k \implies k \geq \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)$ 還是其他對數形式來表示。關鍵在於它們都遵循二分搜尋的原理,這決定了它們的時間複雜度為對數等級。