算法十二：楼尔邦德

悠悠 2022-05-23 20:02 276阅读 0赞

问题描述

给定包含 n 个数的序列 A。

再给出 Q 个询问，每个询问包含一个数 x，询问的是序列 A 中不小于 x 的最小整数是多少（无解输出-1）。

### 输入格式 ###

第一行一个数 n，表示序列长度。

第二行 n 个用空格隔开的正整数，描述序列中的每一个元素。保证这些元素都不会超过 10^9。

第三行一个正整数 Q，表示询问个数。

接下来 Q 行，每行一个正整数 x，描述一个询问。

### 输出格式 ###

输出 Q 行依次回答 Q 个询问，每行一个正整数，表示对应询问的答案。

### 样例输入 ###

3 （序列长度为3）
    3 2 5 （序列）
    6 （询问个数）
    1 （序列中不小于1的最小整数是2）
    2 （序列中不小于2的最小整数是2）
    3 （序列中不小于3的最小整数是3）
    4 （序列中不小于4的最小整数是5）
    5 （序列中不小于5的最小整数是5）
    6 （序列中不小于5的最小整数不存在，返回-1）

### 样例输出 ###

2
    2
    3
    5
    5
    -1

### 提示 ###

\[如果我们先将原序列排序，那么我们就可以在它上面进行二分查找啦！\]

\[STL库中有二分查找的函数\_\_std::lower\_bound\_\_，可以学习一下它的使用。作为初学者，还是建议自己实现二分查找！\]

### 一. 伪代码 ###

![70][]

### 二. 具体实现（C++）  ###

\#include <bits/stdc++.h>  
using namespace std;  
// ================= 代码实现开始 =================  
// 本函数传入数组 a 及所有询问，你需要求解所有询问并一并返回  
// n：序列 a 的长度  
// a：存储了序列 a  
// Q：询问个数  
// query：依次存储了所有询问的参数 x  
// 返回值：一个 vector<int>，依次存放各询问的答案  
vector<int> getAnswer(int n, vector<int> a, int Q, vector<int> query) \{   
 vector<int> ans; //声明返回值ans  
 ans.clear(); //清空ans  
  sort(a.begin(),a.end());/ /由于要进行二分查找，需要保证a有序，因此将a排序  
 for(int i = 0; i < Q; ++i)\{   
 int key = query\[i\]; //key为本次询问的x  
 //进行二分查找  
 int l = -1,r = n,mid;  
while(l+1 < r)\{  
mid = (l+r)>>1;  
if(a\[mid\] < key)  
l = mid;  
else  
r = mid;  
\}  
int pos = r;  
if(pos >= n)  
ans.push\_back(-1);  
else  
ans.push\_back(a\[pos\]);  
\}  
return ans;  
\}  
// ================= 代码实现结束 =================

[70]: /images/20220524/666d7d7203ff40448be24e61d17d75b1.png