二分查找(算法详解+模板+例题)

大家好，欢迎来到IT知识分享网。

一.二分的定义

二分法（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

提示

对于 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[], 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 < 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[]; / * 二分查找函数，寻找元素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

提示

数据范围：

对于 30%的数据，1<n,m<1000，估分和录取线 <10000；

对于 100% 的数据，1<n,m<，估分和录取线< 且均为非负整数。

参考代码：

#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为且m为1时，直接输出结果 if (n ==  && m == 1) { cout << 0 << 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; }