upper_bound和lower_bound函数

以前在求LIS的时候一直在用这两个函数但是没有系统总结总是搞混

lower_bound函数格式：lower_bound(起始地址，结束地址，要查找的数值）

upper_bound函数格式：upper_bound(起始地址，结束地址，要查找的数值）

lower_bound函数：返回第一个大于等于所要查找的数值的地址

upper_bound函数：返回第一个大于所要查找的数值的地址

upper_bound和lower_bound函数同时，我们要注意的是我们必须保证从起始地址到结束地址的一系列数字都是按照升序排列的

当我们求最长上升子序列的时候在运用贪心思想的时候就可以直接使用这两个函数了，但是在求最长下降子序列的时候却需要在一系列按照降序排列的数值中找到第一个小于等于或小于指定数值的位置？

如何实现？

我们只需要在函数中加一个条件即可了。

例如在一个int数组中：

需要改成：

lower_bound(起始地址，结束地址，要查找的数值,greater<int>）

upper_bound(起始地址，结束地址，要查找的数值,greater<int>）

然后需要注意，这两个函数返回的是：地址！地址！地址！

所以我们需要转换一下才能够使用：

1.直接用指针来进行转换（不推荐）

我们知道一个指针变量中储存的是一个变量的地址，所以我们对一个地址所对应的变量进行操作即可了

代码实现：

#include<bits/stdc++.h>
using namespace std;
int n;
int a[1000];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	int *x=lower_bound(a+1,a+n,10);
    *x=100;
	for(int i=1;i<=n;i++) printf("%d ",a[i]);
	return 0;
}
/*
Input:
5
3 7 10 23 45
Output:
3 7 100 23 45
*/

 或者也可以直接对得到的地址返回值的地址处所储存的变量进行操作：

#include<bits/stdc++.h>
using namespace std;
int n;
int a[1000];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	*lower_bound(a+1,a+n,10)=100;
	for(int i=1;i<=n;i++) printf("%d ",a[i]);
	return 0;
}
/*
Input:
5
3 7 10 23 45
Output:
3 7 100 23 45
*/

然而这种方法ROS是不推荐的因为指针方面的知识在OI一般用的很少，稍有不慎便很容易出错

2.使用数组名表示数组的第一个元素的地址来求得该点的数组下标

我们知道，一个数组的名字表示的是这个数组的首个元素的地址。

例如：

int a[10];

我们很容易得到a==&a[0]

所以便有lower_bound(a+1,a+n,10)-a便为我们需要的数字的下标了！

是不是很方便！

但是需要特别注意的是，这两个函数的是指都是二分查找符合条件的值。所以即使没有符合条件的值，由于二分的原因我们仍然会返回一个地址（因情况而异）

总结：本来之前就掌握了这两个函数，但是由于我一直没有写过相关的题解内容，所以每次使用的时候都感到很突兀。所以我最近会整理一下我之前学过的很多算法，整理之余还对这些代码进行了复习

THE END.