lintcode 248. 统计比给定整数小的数的个数二分查找函数 lintcode

给定一个整数数组（下标由 0 到 n-1，其中 n 表示数组的规模，数值范围由 0 到 10000），以及一个查询列表。对于每一个查询，将会给你一个整数，请你返回该数组中小于给定整数的元素的数量。

样例样例 1:输入: array =[1,2,7,8,5] queries =[1,8,5] 输出:[0,4,2] 样例 2:输入: array =[3,4,5,8] queries =[2,4] 输出:[0,1] 挑战可否用一下三种方法完成以上题目。仅用循环方法分类搜索和二进制搜索构建线段树和搜索注意事项在做此题前，最好先完成线段树的构造 and 线段树查询 II 这两道题目。

思路：先排序，后进行二分查找即可
这里有一个函数：lower_bound( )和upper_bound( )
下列知识点原文来自：https://blog.csdn.net/qq_40160605/article/details/80150252
lower_bound( )和upper_bound( )都是利用二分查找的方法在一个排好序的数组中进行查找的。
在从小到大的排序数组中，
lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
upper_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
在从大到小的排序数组中，重载lower_bound()和upper_bound()
lower_bound( begin,end,num,greater() ):从数组的begin位置到end-1位置二分查找第一个小于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
【lintcode 248. 统计比给定整数小的数的个数二分查找函数】upper_bound( begin,end,num,greater() ):从数组的begin位置到end-1位置二分查找第一个小于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

class Solution { public: /** * @param A: An integer array * @param queries: The query list * @return: The number of element in the array that are smaller that the given integer */ vector countOfSmallerNumber(vector &A, vector &queries) { // write your code here vector res(queries.size(),0); if(A.size()<=0) return res; sort(A.begin(),A.end()); for (int i = 0; i < queries.size(); i++) { res[i]=lower_bound(A.begin(),A.end(),queries[i])-A.begin(); } return res; } };