搜索算法：二分查找、DFS 与 BFS
搜索算法是解决问题的基石。从有序数组的二分查找，到图的 DFS/BFS 遍历，再到回溯法的系统搜索，掌握这些框架能解决大量面试问题。
一、二分查找（Binary Search）
二分查找是面试中出现频率最高的算法之一，看似简单，但边界处理非常容易出错。
标准模板
def binary_search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
关键点：
mid = left + (right - left) // 2防止整数溢出while left <= right+right = mid - 1ensures termination- 循环结束时
left是插入位置
找左边界（第一个 ≥ target 的位置）
def left_bound(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return left # 第一个 ≥ target 的位置
找右边界（最后一个 ≤ target 的位置）
def right_bound(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] <= target:
left = mid + 1
else:
right = mid - 1
return right # 最后一个 ≤ target 的位置
旋转排序数组查找（LeetCode 33）
def search_rotated(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
# 判断哪一半是有序的
if nums[left] <= nums[mid]: # 左半有序
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else: # 右半有序
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
二分查找的应用场景：
- 有序数组查找
- 求平方根 / 数值范围搜索
- 寻找满足条件的最值（最大化最小值、最小化最大值）
- 答案具有单调性的问题
二、深度优先搜索（DFS）
递归框架
def dfs(node, visited):
if not node or node in visited:
return
visited.add(node)
# 处理当前节点
for neighbor in node.neighbors:
dfs(neighbor, visited)
图的 DFS（迭代版本）
def dfs_iterative(start, graph):
visited = set()
stack = [start]
while stack:
node = stack.pop()
if node in visited:
continue
visited.add(node)
# 处理节点
for neighbor in reversed(graph[node]): # 反转保持顺序
if neighbor not in visited:
stack.append(neighbor)
岛屿问题（LeetCode 200）
def num_islands(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
count = 0
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0':
return
grid[r][c] = '0' # 标记已访问
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
for i in range(rows):
for j in range(cols):
if grid[i][j] == '1':
count += 1
dfs(i, j)
return count
三、广度优先搜索（BFS）
框架
from collections import deque
def bfs(start, graph):
visited = {start}
queue = deque([start])
while queue:
node = queue.popleft()
# 处理节点
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
最短路径（无权图）
def shortest_path(graph, start, end):
visited = {start}
queue = deque([(start, 0)]) # (节点, 距离)
while queue:
node, dist = queue.popleft()
if node == end:
return dist
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, dist + 1))
return -1
单词接龙（LeetCode 127）
from collections import deque
def ladder_length(begin_word, end_word, word_list):
word_set = set(word_list)
if end_word not in word_set:
return 0
queue = deque([(begin_word, 1)])
while queue:
word, length = queue.popleft()
if word == end_word:
return length
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
next_word = word[:i] + c + word[i+1:]
if next_word in word_set:
word_set.remove(next_word)
queue.append((next_word, length + 1))
return 0
四、回溯法（Backtracking）
回溯是 DFS 的一种特殊形式，用于搜索所有（或部分）解。
通用模板
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
if 剪枝条件:
continue
做选择
backtrack(路径, 新选择列表)
撤销选择
全排列（LeetCode 46）
def permute(nums):
result = []
def backtrack(path, remaining):
if not remaining:
result.append(path[:])
return
for i in range(len(remaining)):
path.append(remaining[i])
backtrack(path, remaining[:i] + remaining[i+1:])
path.pop()
backtrack([], nums)
return result
N 皇后（LeetCode 51）
def solve_n_queens(n):
result = []
board = [['.' for _ in range(n)] for _ in range(n)]
def is_valid(row, col):
# 检查同列
for i in range(row):
if board[i][col] == 'Q':
return False
# 检查左上对角线
i, j = row - 1, col - 1
while i >= 0 and j >= 0:
if board[i][j] == 'Q':
return False
i -= 1
j -= 1
# 检查右上对角线
i, j = row - 1, col + 1
while i >= 0 and j < n:
if board[i][j] == 'Q':
return False
i -= 1
j += 1
return True
def backtrack(row):
if row == n:
result.append([''.join(r) for r in board])
return
for col in range(n):
if is_valid(row, col):
board[row][col] = 'Q'
backtrack(row + 1)
board[row][col] = '.'
backtrack(0)
return result
回溯优化技巧：
- 剪枝：尽早排除不可能的分支
- 状态压缩：用位运算代替布尔数组（如数独）
- 记忆化：对已计算的状态缓存结果
五、BFS vs DFS 选型
| 场景 | 推荐 | 原因 |
|---|---|---|
| 最短路径（无权图） | BFS | 按层扩展，第一次到达即最短 |
| 所有路径 / 全部解 | DFS | 自然递归，便于回溯 |
| 空间受限 | DFS | 栈空间通常小于队列 |
| tree 遍历 | 均可 | BFS 得层序，DFS 得前中后序 |
| 拓扑排序 | BFS / DFS | Kahn 算法或后序逆序 |
六、经典面试题
| 题号 | 题目 | 算法 | 难度 |
|---|---|---|---|
| LeetCode 704 | 二分查找 | 二分 | Easy |
| LeetCode 34 | 在排序数组中查找元素的首末位置 | 二分边界 | Medium |
| LeetCode 33 | 搜索旋转排序数组 | 二分 | Medium |
| LeetCode 200 | 岛屿数量 | DFS/BFS | Medium |
| LeetCode 79 | 单词搜索 | DFS + 回溯 | Medium |
| LeetCode 46 | 全排列 | 回溯 | Medium |
| LeetCode 51 | N 皇后 | 回溯 | Hard |
| LeetCode 127 | 单词接龙 | BFS | Hard |
| LeetCode 130 | 被围绕的区域 | DFS/BFS | Medium |
七、面试常见问题
Q: 二分查找为什么写 left + (right - left) // 2 而不是 (left + right) // 2？
防止整数溢出。在 C++/Java 等语言中，left + right 可能超过 int 最大值。
Q: DFS 和回溯的区别？
DFS 是遍历/搜索策略，回溯是 DFS 的一种应用模式，强调「做选择 → 递归 → 撤销选择」的过程。
Q: BFS 能否处理带权图的最短路径？
不能，需要用 Dijkstra（正权）或 Bellman-Ford（负权）。BFS 只适合无权图或权重相等的情况。
相关文章：
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。