整数二分 C++ 教程（通俗易懂，适合中小学生）

🧠 什么是整数二分？

二分法是一种非常高效的查找方法。它通过不断缩小搜索范围来快速找到答案。就像你在字典里查单词，不用一页一页翻，而是从中间开始找。

✅ 特点：

• 必须在有序的数组中使用
• 每次将搜索范围缩小一半
• 时间复杂度是 O(log n)，比循环快很多

---

🎯 举个生活中的例子：猜数字游戏

想象你和朋友玩一个游戏：

• 你心里想一个1到100之间的数字
• 让朋友猜，每次他猜一个数
• 如果猜大了，你就说“太大了”
• 如果猜小了，你说“太小了”
• 直到猜对为止

用二分法的话，最多只需要7次就能猜出来！

---

🔢 整数二分的C++实现

我们先来看一个简单的例子：
在一个升序排列的数组中查找某个数的位置

#include <iostream>
using namespace std;

// 二分查找函数
int binarySearch(int arr[], int left, int right, int target) {
    // 只要还能继续找（左边界不超过右边界）
    while (left <= right) {
        // 找中间位置
        int mid = (left + right) / 2;

        // 如果找到了目标值
        if (arr[mid] == target) {
            return mid;   // 返回这个位置
        }
        // 如果中间值比目标值小
        else if (arr[mid] < target) {
            left = mid + 1;  // 去右边找
        }
        // 如果中间值比目标值大
        else {
            right = mid - 1; // 去左边找
        }
    }

    // 如果没找到就返回 -1
    return -1;
}

int main() {
    // 创建一个从小到大排好序的数组
    int arr[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    
    // 计算数组长度
    int n = sizeof(arr) / sizeof(arr[0]);
    
    // 要找的目标数字
    int target = 13;
    
    // 调用二分查找函数
    int result = binarySearch(arr, 0, n - 1, target);
    
    // 输出结果
    if (result != -1) {
        cout << "找到了！" << target << "在数组中的第" << result << "个位置（从0开始数）" << endl;
    } else {
        cout << "没有找到这个数字" << endl;
    }

    return 0;
}

---

📚 理解重点（适合中小学生理解）

1. mid = (left + right) / 2 是什么意思？

这是在当前范围内找中间位置。比如在1到10之间找，中间就是(1+10)/2=5.5，取整就是5。

2. 为什么有时候是 left = mid + 1 或者 right = mid - 1？

因为我们已经知道mid位置不是我们要找的数，所以直接跳过它，在它的左边或右边继续找。

3. 什么时候停止？

当left > right的时候，说明整个范围都找完了，还没找到目标值，就说明不存在。

---

🧩 小练习（适合中小学生尝试）

试着修改上面的代码：

1. 把数组改成 {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}
2. 把要找的目标值改成 16
3. 看看输出是什么？

---

🧮 数学原理（进阶）

二分法的核心思想是每次把问题规模减半。

比如有100个数：

• 第一次剩下50个
• 第二次剩下25个
• 第三次剩下12个
• 第四次剩下6个
• 第五次剩下3个
• 第六次剩下1个
• 第七次找到答案

所以100个数最多只需要7次比较就能找到目标值。

---

🧠 学习建议（适合中小学生）

1. 先理解"猜数字"这个游戏的过程
2. 再对照代码看每一步怎么实现这个游戏逻辑
3. 动手改一改数组内容和目标值，观察不同结果
4. 尝试自己写一遍代码，不要复制粘贴

---

❗ 常见错误提醒

1. 数组一定要是排序好的
2. 注意数组下标是从0开始的
3. 不要写错比较符号 < 和 >
4. 不要忘记更新 left 和 right

---

如果你能理解并写出这段代码，恭喜你已经掌握了算法中最重要、最常用的方法之一！👏

需要我解释具体哪一部分吗？或者你想看更多例子吗？我可以给你出题练习哦！📝✏️