Question
You are given a sequence of n integers S and a sequence of different q integers T. Write a program which outputs C, the number of integers in T which are also in the set S.
Input
In the first line n is given. In the second line, n integers are given. In the third line q is given. Then, in the fourth line, q integers are given.
Output
Print C in a line.
Constraints
n ≤ 10000
q ≤ 500
0 ≤ an element in S ≤ 109
0 ≤ an element in T ≤ 109
Sample Input 1
5
1 2 3 4 5
3
3 4 1
Sample Output 1
3
Sample Input 2
3
3 1 2
1
5
Sample Output 2
0
Sample Input 3
5
1 1 2 2 3
2
1 2
Sample Output 3
2
Meaning
使用二分搜索,效率就会很大提高。但是需要注意,二分搜索的前提是数组已经排序好了。那么排序一般最高的效率希尔排序也是0(n1.25),岂不是效率还降低了?相对于O(n),这里题目限制说了
给出的数据就是按升序排列的,那么时间复杂度就是0(qlogn)
给出的数据就是按升序排列的,那么时间复杂度就是0(qlogn)
Coding
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include<iostream> #include<cstdio> using namespace std; int A[100005]; int BinarySearch(int a[], int size, int key) { int l = 0; int r = size - 1; while (l <= r) { int mid = l + (r - l) / 2; if (key == a[mid]) return true; else if (key > a[mid]) l = mid + 1; else r = mid - 1; } return false;//没有找到 } int main() { int n, q, key, sum = 0; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &A[i]); scanf("%d", &q); for (int i = 0; i < q; i++) { scanf("%d", &key); if (BinarySearch(A,n,key)) sum++; } printf("%d\n", sum); } |
Summary
二分搜索使用前需要对数组进行排序;
标准二分搜索算法:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
int BinarySearch(int a[], int size ,int p){ int L=0; //查找区间的左端点 int R=size -1;//查找区间的的右端点 while(L<=R){ int mid =L+(R-L)/2; if(p == a[mid]) return mid; else if(p>a[mid]) L=mid +1; else R=mid-1; } return -1; } |