目錄
1.題目描述
2.AC
1.題目描述
問題 C: 二分查找右側(cè)邊界
時(shí)間限制:?1.000?Sec??內(nèi)存限制:?128 MB
提交?狀態(tài)
題目描述
請(qǐng)?jiān)谝粋€(gè)有序不遞減的數(shù)組中（數(shù)組中的值有相等的值），采用二分查找，找到最后1次出現(xiàn)值x的位置，如果不存在x請(qǐng)輸出-1。
請(qǐng)注意：本題要求出q個(gè)x，每個(gè)x在數(shù)組中第一次出現(xiàn)的位置。
比如有6個(gè)數(shù)，分別是：1 2 2 2 3 3，那么如果要求3個(gè)數(shù)：3 2 5，在數(shù)組中最后一次出現(xiàn)的位置，答案是：6 4 -1。
輸入
第一行，一個(gè)整數(shù)n，代表數(shù)組元素個(gè)數(shù)（n <= 105）
第二行，n個(gè)整數(shù)，用空格隔開，代表數(shù)組的n個(gè)元素（1<=數(shù)組元素的值<=108）
第三行，一個(gè)整數(shù)q，代表有要求出q個(gè)數(shù)最后一次出現(xiàn)的位置（q<=105）
第四行，q個(gè)整數(shù)，用空格隔開，代表要找的數(shù)（1<=要找的數(shù)<=108）
輸出
按題意輸出位置或者-1。
樣例輸入?Copy文章來源：http://www.zghlxwxcb.cn/news/detail-438628.html
6 1 2 2 2 3 3 3 3 2 5
樣例輸出?Copy文章來源地址http://www.zghlxwxcb.cn/news/detail-438628.html
6 4 -1
2.AC
#include <iostream>
#include <cstdio>
using namespace std;
int n, q;
int a[100005];
int main () {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
scanf("%d", &q);
for (int i = 1; i <= q; i++) {
int x;
scanf("%d", &x);
int l = 1, r = n;
while (l <= r) {
int mid = l + (r - l) / 2;
if (x >= a[mid]) {
l = mid + 1;
} else if (x < a[mid]) {
r = mid - 1;
}
}
if (a[r]==x) printf("%d", r);
else printf("-1");
if (i!=q) printf(" ");
}
}到了這里，關(guān)于問題 C: 二分查找右側(cè)邊界（C++）（二分查找）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
