完整可执行代码见 sun2ot/algorithm-learning

基本思想

将一个规模为 n 的问题，分解为 k 个规模较小的子问题。这些子问题相互独立且与原问题相同。递归求解这些子问题，然后将各子问题的解合并得到原问题的解。

二分搜索

算法思想

算法的核心思想是通过不断缩小搜索范围来逼近目标元素。在每一次迭代中，算法首先计算出中间元素的索引 mid ，然后将其与目标元素进行比较。

  • 如果中间元素等于目标元素，则直接返回中间元素的索引
  • 如果中间元素小于目标元素，则将搜索范围缩小为右半部分，将左边界更新为 mid + 1
  • 如果中间元素大于目标元素，则将搜索范围缩小为左半部分，将右边界更新为 mid - 1
    通过不断缩小搜索范围，最终可以找到目标元素或确定其不存在于数组中。

请注意，二分搜索假设输入的数组已经按升序排列。如果数组未排序，需要在进行二分搜索之前先对数组进行排序。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * 二分查找算法
 * 在有序数组中查找目标元素的索引
 * 
 * @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 循环，待搜索数组的大小减少一半。因此最坏情况下，时间复杂度为 O(logn)O(log_n)

Q&A

[!question] 为什么别的算法书是 mid = (left + right) / 2; ？

这是因为在计算中间索引时，使用 (right - left) / 2 可以避免整数溢出的问题。

假设 left 和 right 都是很大的正整数，它们的和可能会超过 int 类型的最大值。如果我们使用 (right + left) / 2 来计算中间索引，可能会导致溢出错误。通过使用 (right - left) / 2 ，我们可以确保在计算中间索引时不会发生溢出。

棋盘覆盖

问题定义

假设你有一个 2n×2n2^n \times 2^n 大小的棋盘，其中一个方格已经被预先填充（或者说被“覆盖”）。你的任务是使用 L 型的三个方格形状的骨牌（也就是说，它覆盖了一个 2x2 的方格，但是缺少了一个角落）来覆盖剩余的所有方格，且任何 2 个 L 型骨牌不得重叠覆盖，如此使得整个棋盘都被填满。

image.png

算法思想

这个问题可以通过分治算法来解决。基本的思路是将棋盘分成四个更小的棋盘，每个棋盘的大小是原来的一半（指边长为 2 的正方形），则特殊方格必定位于 4 个较小的子棋盘之一。

为了将无特殊方格的子棋盘转化为特殊棋盘，可以用一个 L 型的骨牌覆盖这三个较小棋盘的交汇处。

image.png|200*200

然后，对每个更小的棋盘递归地应用同样的过程，直到达到基本情况，即棋盘的大小为 1×11\times1 。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * 在棋盘上放置覆盖物
 * 
 * @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);
    }
}

请注意，这段代码中假设棋盘的大小为 8×88\times8 ，并且特殊位置的行号和列号为 0。你可以根据需要修改这些值。另外，代码中使用 #define 定义了一些常量，你也可以根据需要进行修改。

最终结果如下：

image.png