C3: 效率的必要性：排序與二分搜尋

天王星軌道站管理著數百萬筆星際航線數據。當你需要在龐大的數據庫中快速找到特定資訊時，暴力搜尋（逐一檢查）將耗費數小時。

作為數據分析師，你需要掌握兩個關鍵技能：

1. 排序：將數據整理成有序狀態
2. 二分搜尋：在有序數據中以驚人速度找到目標

這兩個技術是演算法效率提升的基石，能將搜尋時間從數小時縮短到毫秒！

排序（Sorting）

為什麼需要排序？

• 讓數據更易於理解和分析
• 是許多高效演算法的前置步驟
• 能支援快速搜尋

Python 的排序方法：

# 方法 1：list.sort() - 原地排序
numbers = [5, 2, 8, 1, 9]
numbers.sort()  # 修改原列表
print(numbers)  # [1, 2, 5, 8, 9]
# 方法 2：sorted() - 回傳新列表
numbers = [5, 2, 8, 1, 9]
sorted_numbers = sorted(numbers)  # 不修改原列表
print(numbers)         # [5, 2, 8, 1, 9]
print(sorted_numbers)  # [1, 2, 5, 8, 9]
# 反向排序
numbers.sort(reverse=True)  # [9, 8, 5, 2, 1]

時間複雜度：Python 使用 Timsort 演算法，平均和最壞情況都是 O(N log N)。

二分搜尋（Binary Search）

核心概念：在已排序的序列中，每次將搜尋範圍縮小一半。 效率比較：

• 線性搜尋：O(N) - 最壞情況需檢查所有元素
• 二分搜尋：O(log N) - 1,000,000 筆資料只需約 20 次比較！

運作原理：

已排序陣列：[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
尋找目標：13
步驟 1：檢查中間 (9)，13 > 9，往右半部找
       [11, 13, 15, 17, 19]
步驟 2：檢查中間 (15)，13 < 15，往左半部找
       [11, 13]
步驟 3：檢查中間 (11)，13 > 11，往右半部找
       [13]
步驟 4：找到目標！

二分搜尋模板

def binary_search(arr, target):
    """
    在已排序陣列中搜尋目標值
    回傳：目標的索引，若不存在則回傳 -1
    """
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2  # 避免溢位
        
        if arr[mid] == target:
            return mid  # 找到目標
        elif arr[mid] < target:
            left = mid + 1  # 往右半部找
        else:
            right = mid - 1  # 往左半部找
    
    return -1  # 未找到

⚠️ 常見錯誤：

• 忘記陣列必須已排序
• while left <= right 寫成 while left < right
• 邊界更新錯誤

範例 1：基礎二分搜尋

import sys
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1
# 讀取數據
n = int(sys.stdin.readline())
numbers = list(map(int, sys.stdin.readline().split()))
target = int(sys.stdin.readline())
# 排序（二分搜尋的前提）
numbers.sort()
# 搜尋
index = binary_search(numbers, target)
if index != -1:
    print(f"找到目標：位於索引 {index}")
else:
    print("目標不存在")

範例 2：尋找插入位置

import sys
def find_insert_position(arr, target):
    """
    找到目標應該插入的位置
    使陣列保持有序
    """
    left, right = 0, len(arr)
    
    while left < right:
        mid = left + (right - left) // 2
        
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    
    return left
# 讀取數據
n = int(sys.stdin.readline())
numbers = list(map(int, sys.stdin.readline().split()))
target = int(sys.stdin.readline())
numbers.sort()
position = find_insert_position(numbers, target)
print(f"應插入位置：{position}")

範例 3：計算出現次數

import sys
def count_occurrences(arr, target):
    """計算目標在已排序陣列中出現的次數"""
    
    def find_first():
        left, right = 0, len(arr)
        while left < right:
            mid = left + (right - left) // 2
            if arr[mid] < target:
                left = mid + 1
            else:
                right = mid
        return left
    
    def find_last():
        left, right = 0, len(arr)
        while left < right:
            mid = left + (right - left) // 2
            if arr[mid] <= target:
                left = mid + 1
            else:
                right = mid
        return left
    
    first = find_first()
    last = find_last()
    
    if first < len(arr) and arr[first] == target:
        return last - first
    return 0
# 主程式
n = int(sys.stdin.readline())
numbers = list(map(int, sys.stdin.readline().split()))
target = int(sys.stdin.readline())
numbers.sort()
count = count_occurrences(numbers, target)
print(f"{target} 出現 {count} 次")

範例 4：答案空間上的二分搜尋

import sys
def can_distribute(piles, workers, max_time):
    """
    檢查是否能在 max_time 時間內分配完所有工作
    """
    time_used = 0
    for pile in piles:
        time_used += pile
        if time_used > max_time:
            return False
    return True
def find_minimum_time(piles, workers):
    """
    找到完成所有工作的最小時間
    使用二分搜尋在答案空間上搜尋
    """
    left = max(piles)  # 至少需要處理最大的一堆
    right = sum(piles)  # 最多需要處理所有工作
    
    result = right
    while left <= right:
        mid = left + (right - left) // 2
        
        if can_distribute(piles, workers, mid):
            result = mid  # 可行，嘗試更小的時間
            right = mid - 1
        else:
            left = mid + 1  # 不可行，需要更多時間
    
    return result
# 主程式
n = int(sys.stdin.readline())
piles = list(map(int, sys.stdin.readline().split()))
workers = int(sys.stdin.readline())
min_time = find_minimum_time(piles, workers)
print(f"最小完成時間：{min_time}")

關鍵技術點

#### 1. 二分搜尋的邊界處理

# 標準模板（尋找確切值）
while left <= right:  # 注意是 <=
    mid = left + (right - left) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        left = mid + 1  # 不包含 mid
    else:
        right = mid - 1  # 不包含 mid

#### 2. 尋找邊界的模板

# 尋找第一個 >= target 的位置
while left < right:  # 注意是 <
    mid = left + (right - left) // 2
    if arr[mid] < target:
        left = mid + 1
    else:
        right = mid  # 包含 mid

#### 3. 答案空間上的二分搜尋

適用條件：

• 問題要求找「最小的 k 使得...」或「最大的 k 使得...」
• 答案具有單調性

模板：

def is_valid(k):
    """檢查 k 是否滿足條件"""
    pass
left, right = min_possible, max_possible
while left <= right:
    mid = left + (right - left) // 2
    if is_valid(mid):
        # 根據題目調整
        result = mid
        right = mid - 1  # 或 left = mid + 1
    else:
        left = mid + 1   # 或 right = mid - 1