二分的定义

$首先要明白这个算法的运用范围$
$二分是用于查找一个数在这个数列中所在的位置,$
$比一般的for直接暴力查找要快$
$其原理在于将数组分为2个部分$
$并依次用这个数的大小找出这个数在哪个区间，找到直接停止$
$但是二分在特殊情况下才能使用$
$条件就是这个数列必须是一个递增序列$
$明白了这些，我们给道例题:$
备注:例题来源于洛谷

题目背景

计算机竞赛小组的神牛 V 神终于结束了高考，然而作为班长的他还不能闲下来，班主任老 t 给了他一个艰巨的任务：帮同学找出最合理的大学填报方案。可是 v 神太忙了，身后还有一群小姑娘等着和他约会，于是他想到了同为计算机竞赛小组的你，请你帮他完成这个艰巨的任务。

题目描述

现有 $m$ 所学校，每所学校预计分数线是 $a_i$ 。有 $n$ 位学生，估分分别为 $b_i$ 。

根据 $n$ 位学生的估分情况，分别给每位学生推荐一所学校，要求学校的预计分数线和学生的估分相差最小（可高可低，毕竟是估分嘛），这个最小值为不满意度。求所有学生不满意度和的最小值。

输入格式

第一行读入两个整数 $m$、$n$。$m$ 表示学校数，$n$ 表示学生数。

第二行共有 $m$ 个数，表示 $m$ 个学校的预计录取分数。第三行有 $n$ 个数，表示 $n$ 个学生的估分成绩。

输出格式

输出一行，为最小的不满度之和。

输入输出样例

输入#1

4 3
513 598 567 689
500 600 550

输出#1

32

说明/提示

数据范围：

对于 $30$% 的数据，$1\le n,m\le 1000$，估分和录取线 $\le 10000$。

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

$题目传送门$

分析：

由于$n$很大普通算法查找需要$O(n$ $m)$的时间复杂度

暴力算法无法满足100%的数据要求

这时候就该用二分了

二分的时间复杂度是$O(m$ $logn)$

为满足其所需条件在前面加上一个$sort$即可

$实现代码如下：$

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
#define int long long
int a[10000001],sum,m,n;
//主函数外的变量初值为0
int erfen(int x){
	int l=1,r=m,Min=190000000000000000;
	while(l<=r){
		int y=(l+r)/2;
		if(abs(a[y]-x)<=Min){
			Min=abs(a[y]-x);
		}
		if(x<a[y]){
			r=y-1;
		}else{
			l=y+1;
		}
	}
	return Min;
}//也可以不用函数的直接写在main里
signed main(){
	cin>>m>>n;
	for(int i=1;i<=m;i++)
		cin>>a[i];
	sort(a+1,a+1+m);//快速排序使其变为递增序列
	for(int i=1;i<=n;i++){
		int b;
		cin>>b;
		sum+=erfen(b);
	}
	cout <<sum;
 	return 0;
}

~ $完结撒花$ ~

附：这个是第一个博客，也是比较粗糙
先从最简单的算法开始