蓝桥杯算法精讲：二分查找实战与变种解析

适合人群：蓝桥杯备考生 | 算法竞赛入门者 | 二分查找进阶学习者

目录

一、二分查找核心要点

1. 算法思想

2. 适用条件

3. 算法模板

二、蓝桥杯真题实战

例题1：分巧克力（蓝桥杯2017省赛）

例题2：砍竹子（蓝桥杯2022省赛）

三、二分查找变种与技巧

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

二、蓝桥杯真题实战

例题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. 调整边界：根据块数是否满足条件，动态调整左右边界

例题2：砍竹子（蓝桥杯2022省赛）

题目描述：
给定N棵竹子的高度H[i]，每次操作可选择一棵竹子砍到⌊√(H+1)⌋，求所有竹子砍到1的最少操作次数。

问题分析：

• 逆向思维：从1反向计算每个高度需要多少次操作到达

• 预处理：对每个H[i]，预计算其所有可能的中间值

代码实现：

import math  def min_operations():  N = int(input())  H = list(map(int, input().split()))  max_steps = 0  # 预处理每个竹子的操作链  for h in H:  steps = 0  current = h  while current > 1:  # 逆向计算：current由next_step通过f(x)=x^2-1得到  next_step = math.isqrt(current - 1) + 1  steps += 1  current = next_step  max_steps = max(max_steps, steps)  return max_steps  print(min_operations())  

三、二分查找变种与技巧

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