河北大学程序设计训练营

[TOC]

day08 二分查找

利用二分查找找出所给出的数在数组中的下标

输入格式:

第一行输入n和m表示数组有n个数据，m表示要对m个数进行查找

输出格式:

所有输出在一行完成，行末没有多余空格和多余回车。

输入样例:

1
2
3
5 5
1 2 3 4 5
1 2 3 4 5

输出样例:

1
0 1 2 3 4
  1. 题目注意 注意时间限制50ms 所以能使用 cin 和 cout 会超时 或者关闭同步也可以ios::sync_with_stdio(false); //取消cin和stdin的同步。
  2. 可以使用vector动态数组存储 如果使用数组 要开大一点 不然会 溢出发生 段错误。
  3. 二分查找的前提是数据有序 题目没有给出 但是我们默认他们是排序的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
using namespace std;
int num[1000005];
int binarySearch(int begin,int end,int target){
    while(begin<end){
        int mid = (begin+end)/2;
        if(num[mid]==target) return mid;
        else if(num[mid]<target) begin = mid+1;
        else end = mid-1;
    }return end;
}
int main(){
    int a,b;
    scanf("%d %d",&a,&b);
    for(int i=0;i<a;i++)scanf("%d",&num[i]);
    for(int i=0;i<b;i++){
        scanf("%d",&a);
        if(i>0)printf(" ");
        printf("%d",binarySearch(0,b-1,a));
    }return 0;
}

如果不使用二分查找完成本题的话

map 是一个机器不错的选择方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    ios::sync_with_stdio(false);    //取消cin和stdin的同步
    cin >> n >> m;
    map<int,int> mp;     //mp的key值记录数据，value值记录该数据的所在下标
    for(int i = 0; i < n; i++){
        int temp;
        cin >> temp;
        mp[temp] = i;
    }bool isVirgin = true;    //判断是不是第一次
    for(int i = 0; i < m; i++){
        int temp;
        cin >> temp;
        if(isVirgin){
            printf("%d",mp[temp]);
            isVirgin = false;
        }else printf(" %d",mp[temp]);
    }return 0;
}