search

查找

二分查找

普通二分

二分查找（Binary Search）适用于有序数组或序列

它的目标是快速定位一个目标元素在数组中的位置，基本前提是数组必须已经排序，否则二分查找无法正确地工作

基本想法如下：

• 找到一组有序（一般为升序）数据的中位数，设定一个初始区间，左闭右闭，跟目标数比对

  • 中位数计算公式建议使用：mid = left + (right - left) / 2，不仅能正确反映当前区间的中间位置，还能避免因 left + right 过大而可能引发的整型溢出问题

  • 如果中位数比目标数大：说明目标数在左半边更小的那一半数据中，于是舍弃右半边，找到左半边数据的中位数，重复跟目标数比对

  • 如果中位数比目标数小：同理，舍弃左半边，找到右半边数据的中位数，重复跟目标数比对

• 使用循环重复上面的过程，直到找到目标数为止

  • 进入循环的条件通常为：left <= right，需要保证即使区间内只有一个元素也要跟目标值进行比较

二分查找的效率很高，每次迭代能将范围缩小一半，其时间复杂度一般为 O(log n)，空间复杂度一般为 O(1)

二分变种 - 左边界与右边界搜索

是数组中存在重复元素时的特殊情况，遇到了再整理

回溯

核心概念与特点

什么是回溯？

回溯是一种系统地枚举“决策树”所有可能解的搜索算法，当你在解空间树（每个节点代表一次决策）上做深度优先搜索（DFS）时，遇到不满足约束的分支就“回溯”撤销上一步决策，尝试下一种选择

为什么要用回溯？

• 枚举型问题：求子集、组合、排列、八皇后、数独等，需要把所有可能性跑一遍

• 约束搜索：在搜索过程中，可以对当前部分解进行“剪枝”（Pruning），极大减少无效分支

回溯 vs 纯暴力

纯暴力枚举通常两层、三层循环写死，遇到 k 可变时代码膨胀

回溯写一个“模板”，就能适应任意深度的决策；加上剪枝，效率往往远胜暴力

回溯的五要素

• 路径（path）：当前已经做出的所有选择

• 选择列表（choices）：当前节点可做的所有决策

• 结束条件（end condition）：路径凑满、或无更多选择

• 剪枝（pruning）：遇到不满足约束的部分解，提前 return

• 回退（backtrack）：在递归完成后，撤销最后的选择，尝试下一个