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

拼搏现实的明天。 2023-07-07 12:49 9阅读 0赞

给定一个整数数组 （下标由 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,得到找到数字在数组中的下标。

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<int> countOfSmallerNumber(vector<int> &A, vector<int> &queries) {
        
            // write your code here 
            vector<int> 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;
        }
    };