Skip to content

搜索

DFS

最常用的搜索算法，一般用递归实现。

BFS

状态空间中的BFS搜索，和图上的BFS很类似，都可以用队列来实现。

伪代码： 

bfs(s) {
  q = new queue()
  q.push(s), visited[s] = true
  while (!q.empty()) {
    u = q.pop()
    for each edge(u, v) {
      if (!visited[v]) {
        q.push(v)
        visited[v] = true
      }
    }
  }
}

二分搜索

这个也简单，非常常用。

int binary_search(int start, int end, int key) {
  int ret = -1;  // 未搜索到数据返回-1下标
  int mid;
  while (start <= end) {
    mid = start + ((end - start) >> 1);  // 直接平均可能会溢出，所以用这个算法
    if (arr[mid] < key)
      start = mid + 1;
    else if (arr[mid] > key)
      end = mid - 1;
    else {  // 最后检测相等是因为多数搜索情况不是大于就是小于
      ret = mid;
      break;
    }
  }
  return ret;  // 单一出口
}

Meeting in the middle

对于规模较小，但暴力又差一点的问题（一个特征是某些测试便刚好N为最大规模的一半），有时可以用这个优化办法。主要思想是将整个搜索过程分成两半，分别搜索，最后将两半的结果合并。

习题

模拟

模拟就是用程序来模拟题目中发生的操作。

模拟题的特点是虽然算法没有难度，但往往代码量大，逻辑复杂，因此容易出错（这点上和实际的应用程序是比较像的）。有一些方法可以提高正确率：

  • 多多手工模拟，保证对题义和corner case理解全面。
  • 模块化、函数化，将公用的概念和操作提取出来。
  • 分步骤、分模块测试。
  • 要找到关键的点，或者不变量（invariants），往往可以简化问题。

习题

搜索与模拟习题