適合人群：藍橋杯備考生 | 算法競賽入門者 | 二分查找進階學習者

目錄

一、二分查找核心要點

1. 算法思想

2. 適用條件

3. 算法模板

二、藍橋杯真題實戰

例題：分巧克力（藍橋杯2017省賽）

三、二分查找變種與技巧

1. 查找左邊界

2. 查找右邊界

四、常見錯誤與注意事項

五、藍橋杯進階練習題

---

一、二分查找核心要點

1. 算法思想

二分查找（Binary Search）是一種在有序序列中快速定位目標的算法，通過不斷縮小搜索范圍，將時間復雜度從O(n)降至O(log n)。

2. 適用條件

• 有序性：數據必須有序（升序或降序）

• 單調性：問題的解空間具有單調性（如求最大值最小、最小值最大）

3. 算法模板

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  # 未找到  

二、藍橋杯真題實戰

例題：分巧克力（藍橋杯2017省賽）

題目描述：
有N塊巧克力，每塊大小為H[i]×W[i]。需切割出K塊大小相同的正方形，求最大邊長。

問題分析：

• 單調性：邊長越大，能切出的塊數越少

• 二分目標：尋找滿足塊數≥K的最大邊長

代碼實現：

def max_chocolate_size():  N, K = map(int, input().split())  H = []  W = []  for _ in range(N):  h, w = map(int, input().split())  H.append(h)  W.append(w)  # 二分范圍：最小1，最大巧克力邊長上限  left, right = 1, max(max(H), max(W))  ans = 0  while left <= right:  mid = (left + right) // 2  cnt = 0  # 當前邊長能切出的總塊數  for i in range(N):  cnt += (H[i] // mid) * (W[i] // mid)  if cnt >= K:  # 提前終止循環  break  if cnt >= K:  ans = mid  # 記錄可行解  left = mid + 1  # 嘗試更大的邊長  else:  right = mid - 1  # 邊長過大，縮小范圍  return ans  print(max_chocolate_size())  

代碼解析：

1. 二分初始化：左邊界為1，右邊界取所有巧克力的最大邊長

2. 計算塊數：對每塊巧克力計算能切出的塊數，累加直至超過K

3. 調整邊界：根據塊數是否滿足條件，動態調整左右邊界

三、二分查找變種與技巧

1. 查找左邊界

場景：數組中存在重復元素，找到第一個等于target的位置。

def left_bound(arr, target):  left, right = 0, len(arr) - 1  while left <= right:  mid = left + (right - left) // 2  if arr[mid] < target:  left = mid + 1  else:  right = mid - 1  # 壓縮右邊界  # 檢查left是否越界或找到目標  return left if left < len(arr) and arr[left] == target else -1  

2. 查找右邊界

場景：找到最后一個等于target的位置。

def right_bound(arr, target):  left, right = 0, len(arr) - 1  while left <= right:  mid = left + (right - left) // 2  if arr[mid] <= target:  left = mid + 1  # 壓縮左邊界  else:  right = mid - 1  # 檢查right是否有效  return right if right >=0 and arr[right] == target else -1  

四、常見錯誤與注意事項

1. 整數溢出：使用mid = left + (right - left) // 2而非(left + right)//2

2. 邊界更新：確保每次循環邊界必然縮小，防止死循環

3. 終止條件：while left <= right與left = mid + 1/right = mid -1配對使用

4. 返回值驗證：最終結果需檢查是否有效（如索引是否越界）

五、藍橋杯進階練習題

1. 數的范圍（模板題）：藍橋杯題庫

2. 旋轉數組的最小值（變種）：藍橋杯2021省賽

3. 在排序數組中查找元素的第一個和最后一個位置：LeetCode 34