CSP-J 算法基础 二分查找与二分答案

前言

在算法的世界里，二分查找是一种经典的、非常高效的搜索方法，通常用于在有序数组中快速定位某个目标值。而“二分答案”则更进一步，将二分思想运用于更广泛的问题领域，通过不断缩小搜索范围，逐步逼近一个最优解或找到某个满足特定条件的临界值。

二分查找与二分答案作为算法基础的核心思想，在CSP-J考试中频繁出现，掌握这两种方法不仅能够帮助我们解决查找问题，还能有效应对最小化、最大化及临界点等复杂问题。

二分思想

二分思想（也称为二分法或二分查找）是一种常用的算法思想，特别适用于在有序数组或问题空间中查找特定元素或解的场景。核心思想是通过每次将问题的范围对半缩小，从而迅速逼近目标值。这种思想能够大大减少查找的次数，提升效率。

二分思想的工作原理

1. 初始状态：假设有一个已经排序的数组或问题空间，我们要在其中查找某个目标元素或特定的解。
2. 中间点选择：计算当前区间的中间位置，并将这个中间值与目标值进行比较。
3. 范围缩小：
   • 如果中间值等于目标值，查找结束。
   • 如果中间值大于目标值，那么目标值一定在中间值左侧，因此将搜索范围缩小到左半部分。
   • 如果中间值小于目标值，则将搜索范围缩小到右半部分。
4. 重复上述过程，每次将查找范围对半缩小，直到找到目标值或查找范围为空。

二分思想的好处

1. 高效性：二分查找的时间复杂度为 O(log n)，远优于 O(n) 的线性查找。特别是在大规模数据集或搜索空间中，二分法能够显著加快查找速度。
2. 简洁性：算法逻辑简单清晰，易于理解和实现。
3. 应用广泛：二分思想不仅可以用于数组查找，还可以用于求解数学问题、优化问题（如在函数的单调区间内查找极值）、搜索阈值等各种场景。

二分思想的应用场景

• 有序数组查找：在一个已排序的数组中查找目标元素。
• 问题求解：例如在一定范围内查找某个满足条件的数值（如平方根的近似值、最优解的逼近等）。
• 搜索阈值：确定一个系统能够承受的最大负荷、最小资源需求等。

总的来说，二分思想的核心优势在于它能够大大减少搜索的次数，使得在大规模问题中表现尤为优异。

编程实现二分算法

二分查找算法的思考过程

假设我们有一个有序的数组 arr = [1, 3, 7, 9, 12, 15, 18, 20, 23, 27]，我们想要找到数字 15。

步骤一：初始化查找范围

• 初始范围是整个数组，即索引 0 到 9，中间索引为 (0 + 9) / 2 = 4（向下取整）。
• 比较 arr[4] = 12 和 15，因为 12 < 15，所以目标一定在右半部分。

步骤二：缩小范围

• 新的查找范围是索引 5 到 9，新的中间索引为 (5 + 9) / 2 = 7。
• 比较 arr[7] = 20 和 15，因为 20 > 15，所以目标在左半部分。

步骤三：再次缩小范围

• 新的查找范围是索引 5 到 6，新的中间索引为 (5 + 6) / 2 = 5。
• 比较 arr[5] = 15 和 15，找到了目标，算法结束。

二分查找过程中的索引变化：

1. 初始查找范围 [0, 9]，中间索引 4，比较结果 arr[4] = 12。
2. 缩小范围 [5, 9]，中间索引 7，比较结果 arr[7] = 20。
3. 缩小范围 [5, 6]，中间索引 5，找到 arr[5] = 15。

C语言实现二分查找

#include <stdio.h>

// 二分查找函数，返回目标元素的索引，找不到则返回 -1
int binary_search(int arr[], int size, int target) {
    int low = 0;
    int high = size - 1;

    while (low <= high) {
        // 计算中间索引
        int mid = low + (high - low) / 2;

        // 比较中间值与目标值
        if (arr[mid] == target) {
            return mid;  // 找到目标值，返回索引
        } else if (arr[mid] < target) {
            low = mid + 1;  // 目标值在右半部分
        } else {
            high = mid - 1;  // 目标值在左半部分
        }
    }
    return -1;  // 未找到目标值
}

int main() {
    int arr[] = {1, 3, 7, 9, 12, 15, 18, 20, 23, 27};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 15;

    int result = binary_search(arr, size, target);
    if (result != -1) {
        printf("目标值 %d 在数组中的索引是 %d\n", target, result);
    } else {
        printf("目标值 %d 未在数组中找到\n", target);
    }

    return 0;
}

代码分析

• 输入：有序数组 arr、数组大小 size、要查找的目标值 target。
• 输出：如果找到目标值，返回它的索引；否则返回 -1。
• 核心逻辑：在 while 循环中不断将搜索范围对半缩小，直到找到目标值或搜索范围为空。

算法复杂度

• 时间复杂度：O(log n)，因为每次都将搜索范围减半。
• 空间复杂度：O(1)，只使用了固定的几个变量。

二分答案

“二分答案”其实是指通过不断缩小一个区间，直到找到最优解的思想。这不仅仅适用于查找某个特定值，还可以用于在某个区间内寻找一个最优解（例如最大值、最小值、最优条件等）。这种方法常见于优化问题或数学问题中，通过二分法逐步逼近目标答案。

二分答案的过程：

1. 初始化一个区间：首先确定一个包含所有可能答案的初始区间（比如 [L, R]）。
2. 中间点：每次将区间一分为二，计算出中间点（mid）。
3. 判断最优方向：根据具体问题的特性，判断中间点是否满足最优解。如果没有满足，通过某种条件判断应该向左或向右缩小区间。
4. 缩小区间：不断缩小范围，将搜索区间一分为二，直到区间足够小或者满足给定的精度。
5. 最终解：当区间足够小，就能确定最优解在这个区间中。

通俗举例：

• 假设你要找一个水池的最低点，水池有一个连续的坡度变化，你可以通过二分法来逐步缩小范围。首先在两端测试，判断哪个方向会更低，然后每次在中间位置进行测试，逐步将范围缩小，直到找到最低点。

适用场景：

• 最小化/最大化问题：例如在某个范围内找到最小值或最大值。
• 临界问题：找到一个满足某个条件的临界值，例如寻找某个值恰好满足某个约束条件。

这种“二分答案”思想应用广泛，用于求解具有连续性或单调性的问题，通过逐步缩小范围逼近最优解。

编程实现二分答案

下面是一个二分答案的C代码示例，解决了一个简单的最小值问题，并在每次迭代时使用 printf 打印出相关变量的值。

假设我们在某个范围内寻找一个满足条件的最小值，并逐步缩小范围直到找到答案。例子中，我们要找到某个数 x，使得 x*x 大于等于一个给定值 target。

C代码示例：

#include <stdio.h>

int binary_answer(int target) {
    int low = 0;
    int high = target;
    int ans = -1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        // 打印调试信息
        printf("low = %d, high = %d, mid = %d, mid*mid = %d\n", low, high, mid, mid * mid);

        // 判断 mid*mid 是否满足条件
        if (mid * mid >= target) {
            ans = mid;   // 当前 mid 可能是答案
            high = mid - 1;  // 尝试更小的 mid
        } else {
            low = mid + 1;  // mid*mid 太小，尝试更大的 mid
        }
    }

    return ans;  // 返回满足条件的最小解
}

int main() {
    int target = 25;  // 要寻找 x*x >= 25 的最小 x
    int result = binary_answer(target);

    printf("满足条件的最小值是 %d\n", result);
    return 0;
}

输出示例：

当运行这个代码时，printf 会打印每次循环中的 low、high、mid 以及 mid*mid 的值。假设 target = 25，输出结果如下：

low = 0, high = 25, mid = 12, mid*mid = 144
low = 0, high = 11, mid = 5, mid*mid = 25
low = 0, high = 4, mid = 2, mid*mid = 4
low = 3, high = 4, mid = 3, mid*mid = 9
low = 4, high = 4, mid = 4, mid*mid = 16
low = 5, high = 4, mid = 5, mid*mid = 25
满足条件的最小值是 5

代码说明：

• low 和 high 初始化为搜索范围的起始值和目标值。
• mid 是每次迭代时的中间点，通过 low + (high - low) / 2 计算。
• 我们通过 mid * mid 和 target 比较来判断是否满足条件。
  • 如果 mid * mid >= target，说明 mid 可能是答案，并继续尝试更小的值。
  • 如果 mid * mid < target，则调整 low 向右侧逼近。
• 最终返回满足 mid * mid >= target 的最小 mid。

这个二分答案的例子展示了如何通过逐步缩小区间找到满足条件的最优解，并通过 printf 输出了每次迭代中的关键变量。

总结

二分查找与二分答案是算法中的重要工具，其高效性源于每次都将搜索范围对半分，快速缩小查找范围。在CSP-J考试的算法基础部分，掌握这两种二分思想的应用，不仅仅局限于查找问题，还可以处理复杂的最优解和临界值问题。通过熟练运用二分查找，我们能够以 O(log N) 的时间复杂度解决诸多问题，提升算法效率，成为解决CSP-J比赛题目中的重要武器。