一、什么是二分查找？

       二分查找是一种高效的查找算法，就像玩”猜数字”游戏一样：每次猜中间的数字，根据提示”大了”或”小了”缩小范围，直到猜中。

二、二分查找的基本思想

1. 前提条件：数据必须是有序的（从小到大或从大到小排列）

2. 核心思想：每次将查找范围缩小一半

3. 步骤：

   • 确定查找范围的左右边界

   • 计算中间位置

   • 比较中间元素与目标值

   • 根据比较结果调整左右边界

三、生活中的例子

       想象你在字典中查找单词：

1. 打开字典到中间一页

2. 如果要找的单词在中间页之前，就只查看前半部分

3. 否则查看后半部分

4. 重复这个过程直到找到单词

四、算法实现（C++版）

#include <bits/stdc++.h>

using namespace std;

int binarySearch(int arr[], int size, int target) {
    int left = 0;
    int right = size - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2; // 防止溢出
        
        if (arr[mid] == target) {
            return mid; // 找到目标，返回索引
        } else if (arr[mid] < target) {
            left = mid + 1; // 目标在右半部分
        } else {
            right = mid - 1; // 目标在左半部分
        }
    }
    
    return -1; // 没有找到
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11, 13};
    int size = 7;
    int target = 7;
    
    int result = binarySearch(arr, size, target);
    
    if (result != -1) {
        cout << "目标值 " << target << " 在数组中的索引是: " << result << endl;
    } else {
        cout << "目标值 " << target << " 不在数组中" << endl;
    }
    
    return 0;
}

五、关键点讲解

1. 为什么需要有序数组？

   • 只有有序才能确定目标值在中间值的左边还是右边

2. 为什么用 mid = left + (right – left)/2 而不是 (left+right)/2？

   • 防止left和right很大时相加导致整数溢出

3. 循环条件为什么是 left <= right？

   • 当left == right时，还有一个元素需要检查

4. 时间复杂度：O(log n) —— 非常高效！

六、练习题

1. 在有序数组 {2, 4, 6, 8, 10, 12, 14} 中查找数字 10，写出查找过程

2. 如果数组中有重复元素，如何找到第一个或最后一个出现的位置？

3. 尝试自己编写代码实现二分查找

七、常见错误

1. 忘记更新left或right导致无限循环

2. 初始right值设置错误（应该是size-1不是size）

3. 使用无序数组进行二分查找

记住：二分查找的关键是每次将搜索范围减半，这是它比简单遍历快得多的原因！

八、作业

疑问1：为什么使用 mid = left + (right – left)/2 而不是 (left + right)/2？

直观理解

两种方法在数学上是等价的：

left + (right - left)/2 
= left + right/2 - left/2 
= left/2 + right/2 
= (left + right)/2

但在编程中，它们对计算机来说是不一样的！

关键区别：整数溢出问题

当 left 和 right 都是很大的数时，(left + right) 可能会超过整数类型的最大值（溢出），而 (right – left) 不会。

例子说明

假设我们使用 int 类型（最大值约21亿），且：

left = 2,000,000,000
right = 2,100,000,000

方法1：(left + right)/2

left + right = 4,100,000,000 → 超过了int最大值(2,147,483,647)！
计算结果会溢出变成负数

方法2：left + (right – left)/2

right - left = 100,000,000 (安全)
(right - left)/2 = 50,000,000
left + 50,000,000 = 2,050,000,000 (完全正确)

#include <iostream>
using namespace std;

int main() {
    int left = 2000000000;
    int right = 2100000000;
    
    // 不安全的方法
    int mid_unsafe = (left + right) / 2;
    cout << "不安全的方法结果: " << mid_unsafe << endl;
    
    // 安全的方法
    int mid_safe = left + (right - left) / 2;
    cout << "安全的方法结果: " << mid_safe << endl;
    
    return 0;
}

输出结果：

不安全的方法结果: -97483648  (错误的结果！)
安全的方法结果: 2050000000  (正确的结果)

为什么信息学奥赛要注意这个？

1. 竞赛中经常需要处理大数据集

2. 测试用例可能故意设计大数来考察这个细节

3. 这是专业程序员和初学者之间的一个重要区别

记忆技巧

把 left + (right - left)/2 想象成：
“从left出发，向右走一半的距离”

就像测量一段距离：

• 不是把两端坐标相加除以二

• 而是从起点出发，走一半的路程