完整可执行代码见 sun2ot/algorithm-learning
基本思想
将一个规模为 n 的问题，分解为 k 个规模较小的子问题。这些子问题相互独立且与原问题相同。递归求解这些子问题，然后将各子问题的解合并得到原问题的解。
二分搜索
算法思想
算法的核心思想是通过不断缩小搜索范围来逼近目标元素。在每一次迭代中，算法首先计算出中间元素的索引 mid ，然后将其与目标元素进行比较。
- 如果中间元素等于目标元素，则直接返回中间元素的索引
- 如果中间元素小于目标元素，则将搜索范围缩小为右半部分，将左边界更新为
mid + 1 - 如果中间元素大于目标元素，则将搜索范围缩小为左半部分，将右边界更新为
mid - 1通过不断缩小搜索范围，最终可以找到目标元素或确定其不存在于数组中。
请注意，二分搜索假设输入的数组已经按升序排列。如果数组未排序，需要在进行二分搜索之前先对数组进行排序。
代码实现
/** * 二分查找算法 * 在有序数组中查找目标元素的索引 * * @param nums 有序数组 * @param size 数组大小 * @param target 目标元素 * @return 目标元素的索引，如果不存在则返回-1 */int binarySearch(int nums[], int size, int target) {
int left = 0; // 左边界 int right = size - 1; // 右边界
while (left <= right) { // 因为是升序，所以可以保证 right>=left int mid = left + (right - left) / 2;
if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } }
return -1; // 如果目标元素不存在于数组中，则返回-1}复杂度分析
每执行一次 while 循环，待搜索数组的大小减少一半。因此最坏情况下，时间复杂度为
Q&A
[!question] 为什么别的算法书是
mid = (left + right) / 2;？
这是因为在计算中间索引时，使用 (right - left) / 2 可以避免整数溢出的问题。
假设 left 和 right 都是很大的正整数，它们的和可能会超过 int 类型的最大值。如果我们使用 (right + left) / 2 来计算中间索引，可能会导致溢出错误。通过使用 (right - left) / 2 ，我们可以确保在计算中间索引时不会发生溢出。
棋盘覆盖
问题定义
假设你有一个 大小的棋盘，其中一个方格已经被预先填充（或者说被“覆盖”）。你的任务是使用 L 型的三个方格形状的骨牌（也就是说，它覆盖了一个 2x2 的方格，但是缺少了一个角落）来覆盖剩余的所有方格，且任何 2 个 L 型骨牌不得重叠覆盖，如此使得整个棋盘都被填满。
算法思想
这个问题可以通过分治算法来解决。基本的思路是将棋盘分成四个更小的棋盘，每个棋盘的大小是原来的一半（指边长为 2 的正方形），则特殊方格必定位于 4 个较小的子棋盘之一。
为了将无特殊方格的子棋盘转化为特殊棋盘，可以用一个 L 型的骨牌覆盖这三个较小棋盘的交汇处。
然后，对每个更小的棋盘递归地应用同样的过程，直到达到基本情况，即棋盘的大小为 。
代码实现
/** * 在棋盘上放置覆盖物 * * @param tr 当前棋盘的左上角行坐标(row) * @param tc 当前棋盘的左上角列坐标(column) * @param dr 特殊方格行坐标 * @param dc 特殊方格列坐标 * @param size 当前棋盘的大小 */void chessboard(int tr, int tc, int dr, int dc, int size) { if (size == 1) { return; }
int t = tile++; // L型骨牌编号, 自增确保编号唯一 int s = size / 2; // 分割后棋盘大小
// 处理左上角子棋盘 if (dr < tr + s && dc < tc + s) { // 特殊方格在此棋盘中, 直接递归处理 chessboard(tr, tc, dr, dc, s); } else { // 特殊方格不在此棋盘中, 先覆盖再处理 board[tr + s - 1][tc + s - 1] = t; // 用t号L型骨牌覆盖右下角方格 chessboard(tr, tc, tr + s - 1, tc + s - 1, s); // 处理其余方格 }
// 处理右上角子棋盘 if (dr < tr + s && dc >= tc + s) { chessboard(tr, tc + s, dr, dc, s); } else { board[tr + s - 1][tc + s] = t; // 覆盖左下角 chessboard(tr, tc + s, tr + s - 1, tc + s, s); }
// 处理左下角子棋盘 if (dr >= tr + s && dc < tc + s) { chessboard(tr + s, tc, dr, dc, s); } else { board[tr + s][tc + s - 1] = t; // 覆盖右上角 chessboard(tr + s, tc, tr + s, tc + s - 1, s); }
// 处理右下角子棋盘 if (dr >= tr + s && dc >= tc + s) { chessboard(tr + s, tc + s, dr, dc, s); } else { board[tr + s][tc + s] = t; // 覆盖左上角 chessboard(tr + s, tc + s, tr + s, tc + s, s); }}请注意，这段代码中假设棋盘的大小为 ，并且特殊位置的行号和列号为 0。你可以根据需要修改这些值。另外，代码中使用 #define 定义了一些常量，你也可以根据需要进行修改。
最终结果如下：
如果这篇文章对你有帮助，欢迎分享给更多人！
部分信息可能已经过时
