二分法查找
程序员文章站
2024-03-16 08:34:52
...
二分法适合数据量比较大的适合来用,用来查找数据,所给的数据必须是有序的,可以提前用sort来排好序。
bool erfen(int *a,int left,int right,int num){
while(left<right){
int mid=(left+right)/2;
if(num==a[mid]){
return true;
}
else if(num<a[mid]){
right=mid;
}
else if(num>a[mid]){
left=mid+1;
}
}
return false;
}
如果找到num,就返回true;如果没有找到num,就返回false。可以根据题目的需求来返回自己所需要的值。
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.
A - Linear Search-- Aizu - ALDS1_4_A
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
#include<cstdio>
#include<stdio.h>
#include<string>
#include<iostream>
#include<map>
using namespace std;
#include<algorithm>
bool erfen(int *a,int left,int right,int num){
while(left<right){
int mid=(left+right)/2;
if(a[mid]==num){
return true;
}
else if(a[mid]>num){
right=mid;
}
else if(a[mid]<num){
left=mid+1;
}
}
return false;
}
int main(){
int n,q,a[100005],b[100005],count=0;
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
}
cin>>q;
for(int i=0;i<q;i++){
cin>>b[i];
}
sort(a,a+n);
for(int i=0;i<q;i++){
if(erfen(a,0,n,b[i])){
count++;
}
}
cout<<count<<endl;
return 0;
}
一定要记得先排序!!!
下面这两个题都要用到二分法查找。
推荐阅读
-
二分法查找
-
[二分法]leetcode1157:子数组中占绝大多数的元素(hard)
-
LeetCode 1150. 检查一个数是否在数组中占绝大多数(二分查找)
-
数据结构二分法-给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。
-
在一个数组中查找两个重复出现两次的数
-
桶排序来实现查找一个无序数组中第k个大的元素
-
快速查找一个数字是否出现在40亿个数字中
-
JavaScript 查找有序数列中缺少的最小值
-
C语言实现数组中查找最大值、最小值和第二大值
-
二分查找-006-旋转数组的最小数字