二分查找模板

之前找了很多博客，想找一个万能的二分板子，始终没有找到合适的，后来找同学大佬要了一个（鸣谢大佬！QAQ），现在将其上传，供日后自己学习使用。

int erfen()
{
	int l = 1, r = n, ans;
	while (l <= r)
	{
		int mid = (l + r) >> 1;
		if (check(mid))
		{
			ans = mid;
			l = mid + 1;
		}
		else
			r = mid - 1;
	}
	return ans;
}

说明：

1. check()函数是当满足查找条件以及向最佳答案压缩的方向返回true，不满足条件返回false
2. l = mid + 1;和r = mid - 1;这两个表达式要根据查找目标在数组的左右情况要调换位置
3. 二分实现查找lower_bound的原理：一定要理解这一段！！！比如我们要查找两个数之和等于目标值，返回一个第一个值最小的组合，当我们找到一个满足和等于目标值的时候，我们不仅要记录这个答案(将ans更新)，然后将二分区间向左压缩(前提是数列先按照和大小从小到大排，如果和相同的话按前面的数从小到大排)，看看能不能把区间往压一点！这才是lower_bound的核心！即：找到符合大条件的时候。先将该答案存储作为权宜之计，然后将区间向最优答案压缩，这是靠check函数的诱导来实现的！

• 总而言之：check函数保证是满足查找条件！当满足查找条件后，我们先将ans及时更新，然后根据需要，想我们想让他压缩的方向进行压缩，即l=mid+1，r=mid+1这两个式子根据需要的压缩方向决定！

  	if (check(mid))
  {
  	ans = mid;
  	l = mid + 1;
  }

  一道二分+差分模板题
  
  二分+差分的一道题
  洛谷P1083

  #include <bits/stdc++.h>
  using namespace std;
  //二分+差分数组(+前缀和)
  //传送门：https://www.luogu.com.cn/problem/P1083
  //题解传送门：https://www.luogu.com.cn/blog/1557114139--com/solution-p1083
  int n, m;
  long long a[1000000]; //每天教室的最大使用量
  struct node
  {
      int start;
      int end;
      int cost;
  };
  node ask[1000000];    //记录申请数量
  long long c[1000000]; //差分数组
  bool judge(int num)   //通过二分来查找到底第哪一次出现无法访问
  {
      memset(c, 0, sizeof(c));
      for (int i = 1; i <= num; i++)
      {
          c[ask[i].start] += ask[i].cost;
          c[ask[i].end + 1] -= ask[i].cost;
      } //差分构造
      long long now = 0;
      for (int i = 1; i <= n; i++)
      {
          now += c[i]; // now即代表当日的申请数
          if (now > a[i])
          {
              return true; //因为要查找不满足的第一个值，所以不满足条件的时候返回true（符合条件返回true）
          }
      }
      return false;
  }
  int main()
  {
      scanf("%d%d", &n, &m);
      for (int i = 1; i <= n; i++)
          scanf("%d", &a[i]);
      for (int i = 1; i <= m; i++)
          scanf("%d%d%d", &ask[i].cost, &ask[i].start, &ask[i].end); //读入申请
      if (judge(m) == false)
      {
          printf("0");
          return 0;
      }
      int l = 1, r = m, ans;
      while (l <= r)
      {
          int mid = (l + r) >> 1;
          if (judge(mid))
          {
              ans = mid;
              r = mid - 1; //满足条件时，要向左压缩
          }
          else
              l = mid + 1; //反之向右压缩
      }
      cout << -1 << endl;
      cout << ans;
      return 0;
  }

  贪心+队列模拟+二分的题
  

  #include <bits/stdc++.h>
  using namespace std;
  // https://pintia.cn/problem-sets/1506479836133273600/problems/1506481091208822788
  // 队列模拟+贪心+二分
  #define INF 0x3f3f3f3f
  int cnt = 0;
  int N;
  int trail[100010];
  int main()
  {
      // ios::sync_with_stdio(false);
      // cin.tie(0), cout.tie(0);
      cin >> N;
      for (int j = 0; j < N; j++)
      {
          int remp;
          cin >> remp;
          if (cnt == 0 || trail[cnt] < remp)
          {
              trail[++cnt] = remp;
          }
          else
          {
              int l = 1, r = cnt;
              int ans;
              while (l <= r)
              {
                  int mid = (l + r) >> 1;
                  if (remp < trail [mid])
                  {
                      ans = mid;
                      r = mid - 1;
                  }
                  else
                  {
                      l = mid + 1;
                  }
              }
              trail[ans] = remp;
          }
      }
      cout << cnt;
      return 0;
  }