Contest2990 - [C3]-第九节课-二分查找

2024-08-16 19:00:00
3333-08-16 23:00:00
ACM排行榜 OI排行榜 提交记录
运行中 公开 当前时间:2024-09-20 07:53:33
题目编号 标题
A【入门】二分查找 谢明洋(137Byte+ 156ms)
B【入门】二分查找左侧边界 朱帆帆(252Byte+ 79ms)
C【入门】二分查找右侧边界 赵老师(219Byte+ 51ms)
D【入门】二分查找满足条件的数 吴一鹏(218Byte+ 12ms)
E【基础】同时出现的数 林祺威(268Byte+ 93ms)
F【基础】最满意的方案 陈昌俊(255Byte+ 79ms)

信息与公告

#include<bits/stdc++.h>
using namespace std;
int a[1000011], n, t;
int binFind(int l, int r, int tar){ // 闭区间  
 int ans = -1; 
 while(l <= r){ // 交错时结束 
 int mid = (l+r)>>1;
 if(a[mid] == tar){ // 为目标值 
 ans = mid;
 return ans;
 } else if(a[mid] < tar){ // 一定是目标值的坐标
 l = mid + 1;
 } else { // 一定是目标值的右边 
 r = mid - 1;
 }
 }
 return -1;
}

int main(){
 cin >> n;
 for(int i = 1; i <= n; i ++){
 cin >> a[i];
 }
 cin >> t;
 
 cout << binFind(1, n, t);
}
// 第一题

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+11;
int n, t, arr[N];

int find(int l, int r, int tar){
 
 if(r < l) return -1;
 int ans = -1;
 while(l <= r){
 int mid = (l + r) >> 1;
 // int mid = l + (r - l)/2;
 if(arr[mid] >= tar){
 ans = mid;
 r = mid - 1;
 } else{
 l = mid + 1;
 }
 }
 
 if(arr[ans] == tar) return ans;
 else return -1;
 
}

int main(){
 
 cin >> n;
 for(int i = 1; i <= n; i++){
 cin >> arr[i];
 }
 cin >> t;
 while(t -- ){
 int x;
 scanf("%d", &x);
 printf("%d ",find(1, n, x));
 }
 
 
 return 0;
} 
// 第二题

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+11;
int n, t, arr[N];

int find(int l, int r, int tar){
 
 if(r < l) return -1;
 int ans = -1;
 while(l <= r){
 int mid = (l + r) >> 1;
 // int mid = l + (r - l)/2;
 if(arr[mid] <= tar){
 ans = mid;
 l = mid + 1;
 } else{
 r = mid - 1;
 }
 }
 
 if(arr[ans] == tar) return ans;
 else return -1;
 
}

int main(){
 
 cin >> n;
 for(int i = 1; i <= n; i++){
 cin >> arr[i];
 }
 cin >> t;
 while(t -- ){
 int x;
 scanf("%d", &x);
 printf("%d ",find(1, n, x));
 }
 
 
 return 0;
} 
// 第三题

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+11;
int n, t, arr[N];

int find(int l, int r, int tar){
 
 if(r < l) return -1;
 int ans = -1;
 while(l <= r){
 int mid = (l + r) >> 1;
 // int mid = l + (r - l)/2;
 if(arr[mid] >= tar){
 ans = mid;
 r = mid - 1;
 } else{
 l = mid + 1;
 }
 }
 
 if(arr[ans] >= tar) return ans;
 else return -1;
 
}

int main(){
 
 cin >> n;
 for(int i = 1; i <= n; i++){
 cin >> arr[i];
 }
 cin >> t;
 while(t -- ){
 int x;
 scanf("%d", &x);
 printf("%d ",find(1, n, x));
 }
 
 
 return 0;
} 
// 第四题