#c

C++二分法基础

高效查找与问题求解的基础算法

#c
@鞠大龙
魅客科创中心

CONTENTS

目录

1. 二分法概述

1.1 二分法概述

  • 二分法(Binary Search) : 是一种基于分治思想的高效查找算法
  • 核心思想：每次将查找区间缩小一半，从而将时间复杂度从降低到
  • 基本前提：待查找的数据集合必须具有某种有序性或单调性
  • 二分法的两种主要应用：
    • 二分查找：在有序数组中查找特定元素
    • 二分答案：在一个具有单调性的解空间中寻找满足条件的解
返回目录 信息学 C++二分法基础 魅客科创中心

1.2 二分法的历史与应用

二分法的历史：

  • 最早可追溯到公元前9世纪的中国
  • 1946年由John Mauchly首次用于计算机程序
  • 1962年Hermann Bottenbruch提出了现代形式
  • 至今仍是计算机科学中最基础、最重要的算法之一

二分法的应用领域：

  • 数据库索引查询
  • 机器学习（如决策树）
  • 计算几何
  • 数值计算（如求方程根）
  • 游戏开发（如猜数字游戏）

二分法在计算机科学中的地位：

  • 是算法设计中的基础技巧
  • 是理解"分治"思想的入门算法
  • 是竞赛和面试中的常见题型
  • 是高效算法设计的典范
  • 是解决实际问题的有力工具

二分法的变种：

  • 三分法（用于求解凸/凹函数的极值）
  • 指数搜索（先确定范围再二分）
  • 插值搜索（根据值的分布调整查找点）
  • 分数搜索（用于处理有理数问题）
返回目录 信息学 C++二分法基础 魅客科创中心

2. 二分法的特点

2.1 二分法的特点

  • 高效性：时间复杂度为，比线性搜索快得多
  • 前提条件：要求数据集合具有某种有序性或单调性
  • 稳定性：对于相同的输入，总是产生相同的结果
  • 适用范围：不仅适用于查找问题，还适用于优化问题
  • 实现简单但细节关键：基本思想简单，但实现时需要注意边界条件和循环不变量
  • 空间复杂度低：通常只需要的额外空间
返回目录 信息学 C++二分法基础 魅客科创中心

2.2 二分法的优势与局限性

二分法的优势：

  • 高效：时间复杂度为，可以处理大规模数据
  • 简洁：算法思想清晰，实现相对简单
  • 稳定：不受数据分布影响，性能稳定
  • 通用：可以应用于多种问题类型
  • 易于理解：基本思想直观，易于掌握

二分法的局限性：

  • 有序性要求：要求数据集合有序或具有单调性
  • 随机访问要求：需要能够在时间内访问任意元素
  • 不适合小规模数据：对于小规模数据，线性搜索可能更快
  • 不适合频繁更新的数据：每次更新后可能需要重新排序
  • 实现细节容易出错：边界条件和循环不变量需要特别注意
返回目录 信息学 C++二分法基础 魅客科创中心

2.3 二分法的适用场景

  1. 有序数组中的元素查找
    • 查找特定元素是否存在
    • 查找第一个/最后一个等于特定值的元素
    • 查找第一个大于/小于特定值的元素
  2. 解空间中的最优解查找
    • 最大值最小化问题（如分割数组使最大子数组和最小）
    • 最小值最大化问题（如放置物品使最小间距最大）
    • 满足特定条件的临界值查找
  1. 数值计算
    • 求方程的近似解
    • 计算平方根、立方根等
    • 求函数的零点
  2. 判定问题转化为优化问题
    • 将"是否存在解"转化为"最优解是多少"
    • 通过二分+判定函数解决复杂问题
返回目录 信息学 C++二分法基础 魅客科创中心

2.4 二分法的注意事项与优化

何时使用二分法：

  • 数据集合已经有序或可以预处理为有序
  • 需要在大规模数据中进行高效查找
  • 问题可以转化为寻找满足某条件的临界点
  • 解空间具有单调性
  • 需要将时间复杂度从降低到（ ）,从降低到（ ）

二分法的常见优化：

  • 使用位运算加速中点计算：mid = (left + right) >> 1
  • 避免整数溢出：mid = left + (right - left) / 2
  • 结合缓存机制提高性能
  • 针对特定问题设计专门的判断函数
  • 与其他算法结合使用（如二分+贪心、二分+动态规划）
返回目录 信息学 C++二分法基础 魅客科创中心

3. 二分法的模板代码

3.1 二分法的基本模板

// 在有序数组中查找目标值，返回索引，若不存在则返回-1
int binarySearch(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    
    while (left <= right) {
        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;  // 目标值不存在
}
返回目录 信息学 C++二分法基础 魅客科创中心

3.2 查找第一个等于目标值的元素

// 查找第一个等于目标值的元素，返回索引，若不存在则返回-1
int findFirstEqual(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    int result = -1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] == target) {
            result = mid;  // 记录当前找到的位置
            right = mid - 1;  // 继续向左查找
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }  
    return result;
}
返回目录 信息学 C++二分法基础 魅客科创中心

3.3 查找最后一个等于目标值的元素

// 查找最后一个等于目标值的元素，返回索引，若不存在则返回-1
int findLastEqual(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    int result = -1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] == target) {
            result = mid;  // 记录当前找到的位置
            left = mid + 1;  // 继续向右查找
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}
返回目录 信息学 C++二分法基础 魅客科创中心

3.4 查找第一个大于等于目标值的元素

// 查找第一个大于等于目标值的元素，返回索引，若不存在则返回数组长度
int findFirstGreaterOrEqual(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    int result = nums.size();  // 默认为数组长度，表示所有元素都小于目标值
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] >= target) {
            result = mid;  // 记录当前找到的位置
            right = mid - 1;  // 继续向左查找
        } else {
            left = mid + 1;
        }
    }
    
    return result;
}
返回目录 信息学 C++二分法基础 魅客科创中心

3.5 查找最后一个小于等于目标值的元素

// 查找最后一个小于等于目标值的元素，返回索引，若不存在则返回-1
int findLastLessOrEqual(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    int result = -1;  // 默认为-1，表示所有元素都大于目标值
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] <= target) {
            result = mid;  // 记录当前找到的位置
            left = mid + 1;  // 继续向右查找
        } else {
            right = mid - 1;
        }
    }
    
    return result;
}
返回目录 信息学 C++二分法基础 魅客科创中心

3.6 二分法的递归实现

// 二分查找的递归实现
int binarySearchRecursive(vector<int>& nums, int target, int left, int right) {
    // 基本情况：区间为空
    if (left > right) {
        return -1;
    }    
    int mid = left + (right - left) / 2; 
    if (nums[mid] == target) {
        return mid;  // 找到目标值
    } else if (nums[mid] < target) {
        // 在右半部分递归查找
        return binarySearchRecursive(nums, target, mid + 1, right);
    } else {
        // 在左半部分递归查找
        return binarySearchRecursive(nums, target, left, mid - 1);
    }
}
// 包装函数，提供更简洁的接口
int binarySearch(vector<int>& nums, int target) {
    return binarySearchRecursive(nums, target, 0, nums.size() - 1);
}
返回目录 信息学 C++二分法基础 魅客科创中心

3.7 浮点数二分查找

// 浮点数二分查找，用于求解方程 f(x) = 0
double binarySearchFloat(double left, double right, double epsilon) {
    while (right - left > epsilon) {
        double mid = left + (right - left) / 2;
        
        if (f(mid) == 0) {
            return mid;  // 找到精确解
        } else if (f(mid) * f(left) < 0) {
            // f(mid)和f(left)异号，解在[left, mid]区间
            right = mid;
        } else {
            // f(mid)和f(left)同号，解在[mid, right]区间
            left = mid;
        }
    }
    
    // 返回近似解
    return left;  // 或者返回right，此时两者非常接近
}

// 示例函数f(x)，求解x^2 - a = 0（即求a的平方根）
double f(double x, double a) {
    return x * x - a;
}

// 求a的平方根
double sqrt(double a, double epsilon = 1e-9) {
    if (a < 0) return -1;  // 负数没有实数平方根
    if (a == 0) return 0;
    
    double left = 0;
    double right = max(1.0, a);  // 确保右边界足够大
    
    while (right - left > epsilon) {
        double mid = left + (right - left) / 2;
        
        if (mid * mid <= a) {
            left = mid;
        } else {
            right = mid;
        }
    }
    
    return left;
}
返回目录 信息学 C++二分法基础 魅客科创中心

3.8 二分法的常见错误与注意事项

二分法的常见错误与注意事项

  • 整数溢出：计算mid时，如果left和right都很大，(left + right) / 2可能会溢出。应使用left + (right - left) / 2。
  • 死循环：如果更新条件不当，可能导致死循环。例如，当left = mid时，如果mid计算为(left + right) / 2，可能会导致left不变，陷入死循环。此时应使用mid = left + (right - left + 1) / 2（向上取整）。
  • 边界条件：注意循环条件是left <= right还是left < right，以及退出循环后left和right的含义。
  • 区间定义：明确区间是闭区间[left, right]还是左闭右开区间[left, right)，并保持一致的更新策略。
  • 浮点数精度：处理浮点数时，使用epsilon控制精度，而不是固定的迭代次数。
返回目录 信息学 C++二分法基础 魅客科创中心

3.9 STL方法

对于vector，可以使用lower_bound()和upper_bound()函数。

  • 查找第一个等于或者大于x的元素：lower_bound()，v.lower_bound(x)-v.begin()，x是搜索范围的下界
  • 查找第一个大于x的元素：v.upper_bound(x)，v.upper_bound(x)-v.begin()，x是搜索范围的上界
  • 查找第一个与x相等的元素：v.low_bound(x)且等于x
  • 查找最后一个与x相等的元素：v.upper_bound(x)-1且等于x
  • 查找最后一个等于或小于x的元素：v.upper_bound(x)-1
  • 查找最后一个小于x的元素：v.lower_bound(x)-1
  • 计算x的个数：v.upper_bound(x)-v.lower_bound(x)
返回目录 信息学 C++二分法基础 魅客科创中心

4. 实例分析

4.1 实例分析：二分查找基础应用

问题描述：
给定一个按非递减顺序排列的整数数组nums和一个目标值target，请你在数组中找出目标值的位置，如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

分析：

  • 这是一个典型的二分查找问题
  • 我们需要找到第一个大于等于目标值的元素位置
  • 如果目标值存在，返回其位置；如果不存在，返回它应该被插入的位置
返回目录 信息学 C++二分法基础 魅客科创中心

4.1 实例分析：二分查找基础应用（代码示例）

// 搜索插入位置
int searchInsert(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    int result = nums.size();  // 默认插入到末尾
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] >= target) {
            result = mid;  // 找到一个大于等于target的位置
            right = mid - 1;  // 继续向左查找
        } else {
            left = mid + 1;
        }
    }
    
    return result;
}

代码解析：

  • 初始化result为数组长度，表示如果所有元素都小于目标值，则插入到末尾
  • 在循环中，如果找到大于等于目标值的元素，记录位置并继续向左查找
  • 如果当前元素小于目标值，则在右半部分查找
  • 最终返回找到的第一个大于等于目标值的位置

复杂度分析：

  • 时间复杂度：O(log n)，其中n是数组长度
  • 空间复杂度：O(1)，只使用了常数额外空间
返回目录 信息学 C++二分法基础 魅客科创中心

4.2 实例分析：求平方根

问题描述：
给定一个非负整数，计算并返回的平方根，结果只保留整数部分。

分析：

  • 平方根是一个单调递增函数，适合使用二分查找
  • 对于整数x，其平方根不会超过（当时）
  • 我们需要找到最大的整数k，使得²
返回目录 信息学 C++二分法基础 魅客科创中心

4.2 实例分析：求平方根（代码示例）

// 计算整数平方根
int mySqrt(int x) {
    if (x <= 1) return x;
    
    int left = 1;
    int right = x / 2;
    int result = 0;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        // 使用除法避免溢出
        if (mid <= x / mid) {
            result = mid;  // 记录当前找到的值
            left = mid + 1;  // 继续向右查找
        } else {
            right = mid - 1;
        }
    }
    
    return result;
}

代码解析：

  • 特殊情况处理：如果x≤1，直接返回x
  • 初始化查找范围：[1, x/2]，因为平方根不会超过x/2（当x>1时）
  • 使用除法mid <= x / mid代替乘法mid * mid <= x，避免整数溢出
  • 记录满足条件的最大值，并继续向右查找

复杂度分析：

  • 时间复杂度：O(log x)
  • 空间复杂度：O(1)

注意：对于浮点数平方根，需要使用浮点数二分查找，并控制精度。

返回目录 信息学 C++二分法基础 魅客科创中心

4.3 实例分析：旋转排序数组中的搜索

问题描述：
给定一个经过旋转的排序数组nums和一个目标值target，如果目标值存在于数组中，返回其索引，否则返回-1。旋转排序数组是指将一个排序数组在某个未知的位置进行了旋转，如[0,1,2,4,5,6,7]可能变为[4,5,6,7,0,1,2]。

分析：

  • 旋转排序数组的特点：可以分为两个有序的子数组
  • 关键是确定中间元素属于哪个有序子数组，然后决定在哪个子数组中继续查找
  • 需要根据中间元素与左右边界的关系来判断
返回目录 信息学 C++二分法基础 魅客科创中心

4.3 实例分析：旋转排序数组中的搜索（代码示例）

// 在旋转排序数组中搜索目标值
int search(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] == target) {
            return mid;  // 找到目标值
        }
        
        // 判断mid在哪个有序子数组中
        if (nums[left] <= nums[mid]) {
            // 左半部分有序
            if (nums[left] <= target && target < nums[mid]) {
                // 目标在左半部分
                right = mid - 1;
            } else {
                // 目标在右半部分
                left = mid + 1;
            }
        } else {
</div>

<div class=rdiv>

**代码解析**：
- 首先判断中间元素是否为目标值
- 通过比较`nums[left]`和`nums[mid]`确定哪个子数组有序
- 如果左半部分有序，判断目标值是否在左半部分的范围内
- 如果右半部分有序，判断目标值是否在右半部分的范围内
- 根据判断结果缩小搜索范围

**复杂度分析**：
- 时间复杂度：O(log n)
- 空间复杂度：O(1)

</div>

### 4.4 实例分析：猜数字游戏

<!-- _class: fixedtitleA -->

**问题描述**：
猜数字游戏的规则如下：
- 系统选择一个1到n之间的整数
- 你需要通过询问系统"这个数字是否小于等于x"来猜测这个数字
- 目标是用最少的次数猜出这个数字

**分析**：
- 这是二分查找的一个典型应用
- 每次猜测都可以排除一半的可能性
- 最优策略是每次都猜测当前范围的中间数

### 4.4 实例分析：猜数字游戏（代码示例）

<!-- _class: fixedtitleA cols-2-->

<div class=ldiv>

```cpp
// 猜数字游戏
int guessNumber(int n) {
    int left = 1;
    int right = n;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int result = guess(mid);  // API调用
        
        if (result == 0) {
            return mid;  // 猜对了
        } else if (result < 0) {
            right = mid - 1;  // 猜大了
        } else {
            left = mid + 1;  // 猜小了
        }
    }
    
    return -1;  // 不会执行到这里
}

代码解析：

  • guess(int num)是系统提供的API
    • 返回-1表示猜大了
    • 返回1表示猜小了
    • 返回0表示猜对了
  • 使用二分查找不断缩小范围
  • 每次根据API返回的结果调整搜索范围

复杂度分析：

  • 时间复杂度：O(log n)
  • 空间复杂度：O(1)
  • 猜测次数：最多⌈log₂n⌉次
返回目录 信息学 C++二分法基础 魅客科创中心

5. 练习题推荐

5.1 基础练习题

  1. [POJ 1064] Cable master

    • 难度：★★☆☆☆
    • 描述：给定N条绳子的长度，需要将它们剪成等长的小段，求能得到的最大长度
    • 知识点：浮点数二分查找

  2. [HDU 2141] 今年暑假不AC

    • 难度：★★☆☆☆
    • 描述：在有序数组中查找两个数的和等于目标值
    • 知识点：二分查找基础应用

  3. [CSP-J 2019] 数列

    • 难度：★★☆☆☆
    • 描述：在有序数组中查找满足特定条件的元素
    • 知识点：二分查找变种
返回目录 信息学 C++二分法基础 魅客科创中心

5.2 中级练习题

  1. [USACO 2017 Feb Silver] Why Did the Cow Cross the Road II

    • 难度：★★★☆☆
    • 描述：在旋转排序数组中查找元素
    • 知识点：旋转数组中的二分查找

  2. [NOIP 2014] 生活大爆炸版石头剪刀布

    • 难度：★★★☆☆
    • 描述：在循环关系中使用二分查找
    • 知识点：二分查找的应用

  3. [CSES 1620] Factory Machines

    • 难度：★★★☆☆
    • 描述：计算完成特定任务所需的最短时间
    • 知识点：二分答案的思想
返回目录 信息学 C++二分法基础 魅客科创中心

5.3 高级练习题

  1. [CSP-S 2020] 期末考试

    • 难度：★★★★☆
    • 描述：在多个有序数组中进行二分查找
    • 知识点：二分查找的高级应用

  2. [POJ 3579] Median

    • 难度：★★★★☆
    • 描述：求数对差值的中位数
    • 知识点：二分查找与统计

  3. [HDU 3853] LOOPS

    • 难度：★★★★☆
    • 描述：在概率问题中使用二分查找
    • 知识点：二分查找与概率
返回目录 信息学 C++二分法基础 魅客科创中心

5.4 综合应用题

  1. [NOIP 2015] 运输计划

    • 难度：★★★★★
    • 描述：在图论问题中使用二分查找
    • 知识点：二分查找与图论结合

  2. [USACO 2016 Dec Platinum] Team Building

    • 难度：★★★★★
    • 描述：在动态规划中使用二分查找
    • 知识点：二分查找与动态规划结合

  3. [IOI 2016] Paint

    • 难度：★★★★★
    • 描述：在区间问题中使用二分查找
    • 知识点：二分查找与区间处理
返回目录 信息学 C++二分法基础 魅客科创中心

6. 总结

6.1 总结

二分法的核心要点：

  • 基本思想：

    • 每次将问题规模缩小一半
    • 基于有序性或单调性
    • 时间复杂度为O(log n)

  • 关键技巧：

    • 正确处理边界条件
    • 避免整数溢出
    • 合理设计判断函数
    • 注意浮点数精度

  • 常见应用：

    • 有序数组查找
    • 旋转数组查找
    • 求解数值问题
    • 最优化问题

实践建议：

  1. 编码前：

    • 确认问题是否适合用二分法
    • 明确查找空间的范围
    • 设计好判断函数

  2. 编码时：

    • 选择合适的模板
    • 注意边界条件
    • 处理好整数溢出
    • 考虑特殊情况

  3. 调试时：

    • 检查循环条件
    • 验证边界更新
    • 测试特殊输入
    • 确认结果正确性
返回目录 信息学 C++二分法基础 魅客科创中心

6.2 进阶方向

二分法的扩展：

  1. 三分查找：

    • 用于求解凸/凹函数的极值
    • 每次将范围缩小到1/3

  2. 分数二分：

    • 用于处理分数规划问题
    • 将问题转化为判定问题

  3. 二分图匹配：

    • 在图论中的应用
    • 结合匈牙利算法

  4. 并行二分：

    • 多线程环境下的优化
    • 提高查找效率

实际应用中的注意事项：

  1. 在使用二分法之前，先考虑：

    • 数据规模是否足够大
    • 是否需要频繁更新
    • 是否有更简单的解法

  2. 优化建议：

    • 使用位运算加速
    • 结合其他算法
    • 考虑缓存友好
    • 注意代码可读性

  3. 记住：

    • 简单问题用简单方法
    • 正确性优先于效率
    • 可维护性很重要
返回目录 信息学 C++二分法基础 魅客科创中心
C++二分法基础

#c

演讲者备注不会在演示模式中显示给观众，仅供演讲者参考。 每个关键页面都添加了备注，帮助演讲者更好地讲解内容。

封面页： - 欢迎学生，简要介绍本次课程的主题和目标 - 强调二分法是算法设计中的基础技巧，也是竞赛和面试中的常见题型 - 可以简单提及本课程将从基础概念到实际应用，全面讲解二分法的思想和技巧

目录页： - 简要介绍本次讲座的结构和内容安排 - 可以提及讲座的逻辑流程：从基础概念到具体应用，再到实践建议 - 强调我们将通过多个例子来深入理解二分法的应用 - 提醒学生关注每个部分之间的联系，以及如何将理论应用到实践中

转场页： - 这是一个简单的转场页，用于引入二分法概述部分 - 可以简单提及二分法是算法设计中的重要策略，有着广泛的应用

二分法概述： - 介绍二分法的基本概念和核心思想 - 强调二分法的高效性和应用场景 - 简要提及二分法的历史和发展

二分法的历史与应用： - 介绍二分法的历史背景 - 讨论二分法在不同领域的应用 - 强调二分法的重要性和普遍性

转场页： - 引入二分法的特点部分 - 可以简单提及理解这些特点有助于更好地应用二分法

二分法的特点： - 详细介绍二分法的主要特点 - 强调这些特点如何帮助识别和解决二分法问题 - 解释二分法的优势和局限性

二分法的优势与局限性： - 分析二分法的优势和局限性 - 讨论何时应该选择二分法 - 提供一些优化二分法的思路

二分法的适用场景： - 详细介绍二分法适用的各种场景 - 提供一些实际应用的例子 - 讨论如何识别可以使用二分法的问题

转场页： - 引入二分法的模板代码部分 - 可以简单提及掌握这些模板有助于快速实现二分法算法

二分法的基本模板： - 提供二分法的基本代码模板 - 解释模板中的关键部分 - 强调循环不变量的重要性

查找第一个等于目标值的元素： - 提供查找第一个等于目标值的元素的代码模板 - 解释与基本模板的区别 - 强调处理重复元素的技巧

查找最后一个等于目标值的元素： - 提供查找最后一个等于目标值的元素的代码模板 - 解释与查找第一个等于目标值的元素的区别 - 强调边界条件的处理

查找第一个大于等于目标值的元素： - 提供查找第一个大于等于目标值的元素的代码模板 - 解释与前面模板的区别 - 强调这种模板的应用场景

查找最后一个小于等于目标值的元素： - 提供查找最后一个小于等于目标值的元素的代码模板 - 解释与前面模板的区别 - 强调这种模板的应用场景

二分法的递归实现： - 提供二分法的递归实现代码 - 比较递归实现和迭代实现的优缺点 - 讨论何时选择递归实现

浮点数二分查找： - 提供浮点数二分查找的代码模板 - 解释浮点数二分查找的特点和注意事项 - 讨论精度控制的方法

二分法的常见错误与注意事项： - 列举二分法实现中的常见错误 - 提供避免这些错误的方法 - 强调细节的重要性

转场页： - 引入实例分析部分 - 可以简单提及我们将通过几个经典例子来深入理解二分法

二分查找基础应用： - 详细介绍二分查找的基础应用 - 通过具体例子说明二分查找的实现和应用 - 强调二分查找的效率和适用条件

二分查找基础应用的代码实现： - 提供完整的代码实现 - 解释代码中的关键部分 - 分析算法的时间和空间复杂度

求平方根： - 详细介绍如何使用二分法求平方根 - 解释整数平方根和浮点数平方根的区别 - 强调精度控制的重要性

求平方根的代码实现： - 提供完整的代码实现 - 解释代码中的关键部分 - 分析算法的时间和空间复杂度

旋转排序数组中的搜索： - 详细介绍如何在旋转排序数组中使用二分查找 - 解释旋转排序数组的特点和处理方法 - 强调二分查找在复杂场景中的应用

旋转排序数组中的搜索的代码实现： - 提供完整的代码实现 - 解释代码中的关键部分 - 分析算法的时间和空间复杂度