Binary Search
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)
Coding
#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
二分搜索使用前需要对数组进行排序; 标准二分搜索算法:
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;
}
废江博客 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 转载请注明原文链接:Binary Search
相关文章
- google search_google.com
- stl-二分查找binary_search和sort
- elastic search面试题_elasticsearch实战
- 关闭Win10的Windows Search功能
- dirsearch使用教程_search过去式
- Feep! search:一款面向程序员的搜索引擎,收录信息超 2900 万页!
- ORA-31207: DBMS_LDAP: PL/SQL – Invalid LDAP search time value. ORACLE 报错 故障修复 远程处理
- ORA-07565: sldext: $SEARCH failure ORACLE 报错 故障修复 远程处理
- Search in Rotated Sorted Array II详解程序员
- BINARY SEARCH 的一点说明详解编程语言
- abap自定义屏幕Search Help详解编程语言
- ABAP中BINARY SEARCH详解编程语言
- Search in Rotated Sorted Array II详解编程语言
- js中exec、test、match、search、replace、split用法
- js通过location.search来获取页面传来的参数