menu 李昊天的个人博客
程序设计:算法和数据结构 笔记3——搜索
399 浏览 | 2019-07-09 | 分类:算法笔记 | 标签:算法,学习笔记,搜索

概述

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

线性搜索

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

二分搜索

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

思路

  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 个元素的素组执行线性搜索以及二分搜索时,最坏的情况下运算次数如下

元素数线性搜索二分搜索
1001007
100001000014
1000000100000020

最坏情况下二分搜索的复杂度大概是$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

迭代器

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

可以使用的运算符

运算符效果
++指向下一个迭代器
==,!=判断两个迭代器指向位置是否相等
=将运算符右侧迭代器赋值给左侧迭代器
*返回该位置元素

容器函数

函数名效果
begin()返回容器的开头元素
end()返回容器的最后一个元素
#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<<"  ";
    }
}

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

发表评论

email
web

全部评论 (暂无评论)

info 还没有任何评论,你来说两句呐!