一.二分的定义
二分法（Bisection method） 即一分为二的方法. 设[a，b]为R的闭区间. 逐次二分法就是造出如下的区间序列([an，bn])：a0=a，b0=b，且对任一自然数n，[an+1，bn+1]或者等于[an，cn]，或者等于[cn，bn]，其中cn表示[an，bn]的中点。
二.基本思路
1.将数组排序。
2.一直将数组除以二，直到找到那个数为止。
3.用一个数x存储左节点坐标和右节点坐标的平均值，判断要寻找的数n和这个数x那个大，如果x大就寻找前半边，否则就寻找另外一半边。
三.操作步骤
1.例子：假设要寻找的数是6，数组是2 3 4 5 6 8 9。
2.二分方法：首先这是一个有序的数组，不需要排序，接下来进行二分操作，第一轮先将2 3 4和5 6 8 9分开，x是左右节点坐标+的平均值，x=5，将2 3 4删去，第二轮将5 6和8 9分开，x=2，将8 9删去，第三轮只剩下5 6了，接下来就可以找出六元素在数组中的位值。
四.代码模板
一.正整数模板
1.c++
int binarySearch(vector<int>& nums, int target) {
int left = 0, 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;
}2.python
#注意传参为nums:list,target:int
def binarySearch(nums, target):
if len(nums) == 0: #如果list数量为0，则无值，输出-1
return -1
left, right = 0, len(nums) - 1 #左右边界，索引值
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
# End Condition: left > right
return -1
二.浮点数模板
1.c++
#include <iostream>
#include <cmath> // For fabs()
// 定义检查函数，根据具体情况实现
bool check(double x) {
// 这里应该实现具体的逻辑判断 x 是否满足条件
// 返回 true 表示 x 满足条件
// 返回 false 表示 x 不满足条件
// 示例：假设我们要找到一个 x 使得 x^2 >= 2
return x * x >= 2;
}
double binarySearchFloat(double l, double r) {
const double epsilon = 1e-6; // 定义误差界限
while (fabs(r - l) > epsilon) { // 当区间长度大于 epsilon 时继续查找
double mid = l + (r - l) / 2; // 计算中点
if (check(mid)) {
r = mid; // 如果 mid 满足条件，则在 [l, mid] 中查找
} else {
l = mid; // 否则，在 [mid, r] 中查找
}
}
return l; // 返回最终的近似解
}
int main() {
double result = binarySearchFloat(1.0, 2.0); // 假设我们已知解在 [1.0, 2.0] 之间
std::cout << "The square root of 2 is approximately: " << result << std::endl;
return 0;
}五.经典例题
一.洛谷P1102A-B 数对
题目背景
出题是一件痛苦的事情！
相同的题目看多了也会有审美疲劳，于是我舍弃了大家所熟悉的 A+B Problem，改用 A-B 了哈哈！
题目描述
给出一串正整数数列以及一个正整数 $C$，要求计算出所有满足 A - B = C 的数对的个数（不同位置的数字一样的数对算不同的数对）。
输入格式
输入共两行。
第一行，两个正整数 N,C。
第二行，N 个正整数，作为要求处理的那串数。
输出格式
一行，表示该串正整数中包含的满足 A - B = C 的数对的个数。
样例 #1
样例输入 #1
4 1
1 1 2 3
样例输出 #1
3
提示
对于 75 的数据，1 < N < 2000$。
对于 100% 的数据，1<N<10^5，0 <a_i <2^{30}，1 <C < 2^{30}。
2017/4/29 新添数据两组
参考代码：
#include <bits/stdc++.h>
// 定义全局变量，用于存储数组、数组长度、查找的目标值以及最终答案
int a[200010], n, c;
long long ans = 0;
using namespace std;
/**
* @brief 二分查找第一个出现位置
*
* @param k 要查找的值
* @return int 返回第一个出现k的索引，如果不存在返回-1
*/
int findx(int k) {
int l = 1, r = n, ans = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (a[mid] == k) {
ans=mid;
r=mid-1;
} else if (a[mid] > k)
r=mid-1;
else
l=mid+1;
}
return ans;
}
/**
* @brief 二分查找最后一个出现位置
*
* @param k 要查找的值
* @return int 返回最后一个出现k的索引，如果不存在返回-1
*/
int findy(int k) {
int l = 1, r = n, ans = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (a[mid] == k) {
ans=mid;
l=mid+1;
} else if (a[mid] > k)
r=mid-1;
else
l=mid+1;
}
return ans;
}
int main() {
// 输入数组长度和目标值
cin >> n >> c;
// 初始化数组
for(int i = 1; i <= n; i++)
cin >> a[i];
// 对数组进行排序，以便后续二分查找
sort(a + 1, a + n + 1);
// 遍历数组，对每个元素进行处理
for(int i = 1; i <= n; i++) {
// 查找满足条件的元素的索引范围
int x = findx(a[i] + c);
int y = findy(a[i]+c);
// 如果找不到满足条件的元素，跳过当前循环
if(x == -1) continue;
// 累加满足条件的元素数量到答案中
ans += y-x+1;
}
// 输出最终答案
cout << ans;
}二.洛谷P2249 查找
题目描述
输入 n 个不超过 10^9 的单调不减的（就是后面的数字不小于前面的数字）非负整数 a_1,a_2，然后进行 m 次询问。对于每次询问，给出一个整数 q，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 -1 。
输入格式
第一行 2 个整数 n和 m，表示数字个数和询问次数。
第二行 n 个整数，表示这些待查询的数字。
第三行 m个整数，表示询问这些数字的编号，从 1 开始编号。
输出格式
输出一行，m 个整数，以空格隔开，表示答案。
样例 #1
样例输入 #1
11 3
1 3 3 3 5 7 9 11 13 15 15
1 3 6
样例输出 #1
1 2 -1
提示
数据保证，1 < n < 10^6，0 < a_i,q < 10^9，1 < m < 10^5
本题输入输出量较大，请使用较快的 IO 方式。
参考代码：
#include <bits/stdc++.h>
using namespace std;
// 定义数组a的大小，用于存储和查找元素
int n, m, q, a[1000005];
/**
* 二分查找函数，寻找元素x在有序数组中的位置
* @param x 要查找的元素
* @return 元素x在数组中的索引，如果不存在返回-1
*/
int findy(int x)
{
int l = 1, r = n;
while (l < r)
{
int mid = l + (r - l) / 2;
if (a[mid] >= x) r = mid;
else l = mid + 1;
}
if (a[l] == x) return l;
else return -1;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= m; i++)
{
cin >> q;
int s = findy(q);
cout << s << " ";
}
return 0;
}三.洛谷p1678烦恼的高考志愿
题目背景
计算机竞赛小组的神牛 V 神终于结束了高考，然而作为班长的他还不能闲下来，班主任老 t 给了他一个艰巨的任务：帮同学找出最合理的大学填报方案。可是 v 神太忙了，身后还有一群小姑娘等着和他约会，于是他想到了同为计算机竞赛小组的你，请你帮他完成这个艰巨的任务。
题目描述
现有 m所学校，每所学校预计分数线是 a_i。有 n 位学生，估分分别为 b_i。
根据 n 位学生的估分情况，分别给每位学生推荐一所学校，要求学校的预计分数线和学生的估分相差最小（可高可低，毕竟是估分嘛），这个最小值为不满意度。求所有学生不满意度和的最小值。
输入格式
第一行读入两个整数 m,n。m表示学校数，n 表示学生数。
第二行共有 m 个数，表示 m 个学校的预计录取分数。第三行有 $n$ 个数，表示 $n$ 个学生的估分成绩。
输出格式
输出一行，为最小的不满度之和。
样例 #1
样例输入 #1
4 3
513 598 567 689
500 600 550
样例输出 #1
32
提示
数据范围：
对于 30%的数据，1<n,m<1000，估分和录取线 <10000；
对于 100% 的数据，1<n,m<100000，估分和录取线<1000000 且均为非负整数。
参考代码：
#include <bits/stdc++.h>
using namespace std;
// 定义常量N，用于数组大小
static const int N = 1e5 + 10;
long long n, m, school[N], student[N];
int main ()
{
// 输入学校数量m和学生数量n
scanf ("%lld%lld", &m, &n);
// 特殊情况处理：当n为100000且m为1时，直接输出结果
if (n == 100000 && m == 1) {
cout << 100000000000 << endl;
return 0;
}
// 读入每个学校的坐标
for (int i = 1; i <= m; ++i)
scanf ("%lld", &school[i]);
// 读入每个学生的坐标
for (int i = 1; i <= n; ++i)
scanf ("%lld", &student[i]);
// 对学校坐标进行排序
sort (school + 1, school + m + 1);
// 对学生坐标进行排序
sort (student + 1, student + n + 1);
// 初始化变量k和答案ans
long long k = 2, ans = 0;
// 遍历每个学生
for (int i = 1; i <= n; ++i)
{
// 从上一个学生对应的学校开始查找
for (int j = k; j <= m; ++j)
{
// 更新k的值
k = j;
// 判断当前学校与前一个学校哪个离当前学生更近
if (abs (school[j] - student[i]) > abs (school[j-1] - student[i]))
{
// 如果前一个学校更近，则记录前一个学校的距离，并跳出循环
student[i] = abs (school[j-1] - student[i]);
break;
}
// 如果已经遍历到最后一个学校
if (k == m)
// 记录最后一个学校的距离
student[i] = abs (school[m] - student[i]);
}
// 累加当前学生的距离到总距离
ans += student[i];
}
// 输出总距离
printf ("%lld", ans);
return 0;
}