概述

搜索是从数据集合中找出目标元素的处理。

线性搜索

线性搜索是从数组开头顺次访问个元素，检查给该元素是否与目标值相等。相等则返回元素位置并结束搜索。如果检查完数组还没有发现目标值，则返回一个特殊值来说明。线性搜索的算法效率很低，但适用于任何形式的数据。

二分搜索

二分搜索算法可以利用数据的大小进行高速搜索。二分搜索的前提是 已经排序。

思路：

1. 将整个数组（升序）作为搜索范围
2. 检查位于搜索范围正中央的元素
3. 如果一致则结束
4. 如果不一致则比较大小，小于的话，以前半部分为搜索范围执行第二步。否则以后半部分为范围执行。
5. 如果到最后没找到，就返回特定值，表示未找到

散列法

在散列法中，各元素的存储位置由散列函数决定。散列既是一种数据结构，同时也是一种使用散列表的算法。只需要将关键字（key）带入就可得到对应位置。搜索效率很高。

线性搜索

题目

请编写一个程序，输入包含 n 个整数的数列 s 以及包含 q 个不重复整数数列 T ，输出既包含于 T 又包含于 S 的整数个数 c

输入： 第一行输入 n，第二行输入代表 S 的 n 个整数，第三行输入 q，第四行输入代表 T 的 q 个整数。

输出：用1行输出C

限制： $n\leq1000$，$q\leq500$ ，$0\leq{S,T的元素}\leq{10^9}$，T中元素不重复

输入示例:

5
1 2 3 4 5
3
3 4 1

输出示例：

3

程序

#include<stdio.h>

int  search(int A[],int n, int key){
    int i=0;
    A[n]=key;//通过将最后一个置为key的方法，引入标记，可以提升效率，在处理大数据的时候会有显著效果
    while(A[i]!=key) i++;
    return i!=n;
}
int main(){
    int i,n,A[10001],q,key,sum=0;

    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&A[i]);
    }

    scanf("%d",&q);
    for(i=0;i<q;i++){
        scanf("%d",&key);
        if (search(A,n,key))
        {
            sum++;
        }
        
    }
    printf("%d\n",sum);

    return 0;

}

输出结果

因为线性搜索的算法复杂度为$O(n)$，所以算法的复杂度$O(qn)$

二分搜索

对于含有 n 个元素的素组执行线性搜索以及二分搜索时，最坏的情况下运算次数如下

最坏情况下二分搜索的复杂度大概是$log_2n$

题目

同上题，假设输入有序数列

程序

#include<stdio.h>

int  search(int A[],int n, int key){
    int left=0;
    int right=n-1;
    int mid;
    while(left<right){
        mid=(left+right)/2;
        if(key==A[mid]) return 1;
        if(key>A[mid])left=mid+1;
        else right=mid-1;
    }
    return 0;
}
int main(){
    int i,n,A[10001],q,key,sum=0;

    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&A[i]);
    }

    scanf("%d",&q);
    for(i=0;i<q;i++){
        scanf("%d",&key);
        if (search(A,n,key))
        {
            sum++;
        }
        
    }
    printf("%d\n",sum);

    return 0;

}

运行结果：

散列法

不同于数组的下标索引，可以通过键值直接查到对应值，每一个键值都有一个唯一对应的值

数组索引 a[0],a[1],a[2]……

散列 a[key0],a[key1],a[key2]……

方法：

1. 通过散列函数在键值与值之间建立一个对应的函数关系Hash()
2. 存储位置可以通过 address=Hash(key) 的方式运算出来
3. 在插入和搜索时通过步骤2的方式可以迅速得出键值对应值的存储位置

散列函数

方法中步骤1中所涉及的函数关系叫做散列函数

散列函数在使用的时候应该注意：

• 简单，快速的可以计算出结果

• 在双散列结构中，当多个键值的散列值相同时，即冲突发生时，可以调用hash1() hash2() hash3()……等一系列散列函数得到不同的散列值

STL

迭代器

迭代器是一种对象，可以对容器中对象进行迭代处理，指向容器中的位置

可以使用的运算符

容器函数

#include<iostream>
#include<vector>
using namespace std;
int main(){
    vector<int> v;
    int i;
    for(i=0;i<10;i++){
        v.push_back(i);
    }
    vector<int>::iterator iter;
    for(iter=v.begin();iter!=v.end();iter++){
        cout<<*iter<<"  ";
    }
}