多种方法实现查找
查找
https://www.nowcoder.com/practice/d93db01c2ee44e8a9237d63842aca8aa?tpId=40&&tqId=21531&rp=1&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking
线性查找
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX=100;
int arr[MAX];
bool LinSearch(int n,int target){
for(int i=0;i<n;i++)
if(arr[i]==target)
return true;
return false;
}
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++) //由n控制输入个数
scanf("%d",&arr[i]);
int m;
scanf("%d",&m);
while(m--){ ////由m控制比较个数
int target;
scanf("%d",&target);
if(LinSearch(n, target))
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
二分查找
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX=100;
int arr[MAX];
bool BinarySearch(int n, int target){
int left=0;
int right=n-1;
while(left<=right){
int middle=left+(right-left)/2;
if(arr[middle]<target)
left=middle+1;
else if(arr[middle]>target)
right=middle-1;
else
return true;
}
return false;
}
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++) //由n控制输入个数
scanf("%d",&arr[i]);
sort(arr, arr+n); //二分查找的前提是数组arr要求有序
int m;
scanf("%d",&m);
while(m--){ ////由m控制比较个数
int target;
scanf("%d",&target);
if(BinarySearch(n, target))
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
散列查找
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX=100;
int arr[MAX];
int HashTable[MAX];
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&arr[i]);
HashTable[arr[i]]=true; //出现这个值，就把对应HashTable的值赋值为true
} //由n控制输入个数
int m;
scanf("%d",&m);
while(m--){ ////由m控制比较个数
int target;
scanf("%d",&target);
if(HashTable[target]) //通过target对应HashTable是否有值存在
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
