精华内容
下载资源
问答
  • 线性查找

    2016-12-23 00:27:12
    算法导论练习题2.1-3 考虑如下查找问题: 输入:n个数的一个序列 A = {a1, a2, ..., an} 和一个值 V. ...我的线性伪代码如下: n = A.length for i=1 to n if(v==A[i]) return i i = i + 1 return

    算法导论练习题2.1-3

    考虑如下查找问题:

    输入:n个数的一个序列 A = {a1, a2, ..., an} 和一个值 V.

    输出:下标 i 使得 V = A[ i ] 或者 当 V 不在 A 中出现时,V 为特殊值 NIL.

    我的线性伪代码如下:

    n = A.length
    for i=1 to n
    	if(v==A[i])
    		return i
    	i = i + 1
    return NIL



    展开全文
  • Java线性查找和二分查找。一 线性查找定义:在一列给定的值中进行搜索,从一端开始逐一检查每个元素,直到找到所需元素的过程。线性查找又称为顺序查找。如果查找池是某种类型的一个表,比如一个数组,简单的查找...

    Java线性查找和二分查找。

    一 线性查找

    定义:在一列给定的值中进行搜索,从一端开始逐一检查每个元素,直到找到所需元素的过程。

    线性查找又称为顺序查找。如果查找池是某种类型的一个表,比如一个数组,简单的查找方法是从表头开始,一次将每一个值与目标元素进行比较。最后,或者查找到目标,或者达到表尾,而目标不存在于组中,这个方法称为线性查找。

    Java代码

    public class LSearch

    {

    public static int[] Data = { 12, 76, 29, 22, 15, 62, 29, 58, 35, 67, 58,

    33, 28, 89, 90, 28, 64, 48, 20, 77 }; // 输入数据数组

    public static int Counter = 1; // 查找次数计数变量

    public static void main(String args[])

    {

    int KeyValue = 22;

    // 调用线性查找

    if (Linear_Search((int) KeyValue))

    {

    // 输出查找次数

    System.out.println(“”);

    System.out.println(“Search Time = ” + (int) Counter);

    }

    else

    {

    // 输出没有找到数据

    System.out.println(“”);

    System.out.println(“No Found!!”);

    }

    }

    // —————————————————

    // 顺序查找

    // —————————————————

    public static boolean Linear_Search(int Key)

    {

    int i; // 数据索引计数变量

    for (i = 0; i < 20; i++)

    {

    // 输出数据

    System.out.print(“[" + (int) Data[i] + “]”);

    // 查找到数据时

    if ((int) Key == (int) Data[i])

    return true; // 传回true

    Counter++; // 计数器递增

    }

    return false; // 传回false

    }

    }

    运行结果:

    [12][76][29][22]

    Search Time = 4

    二 折半查找

    定义:二分查找又称折半查找,它是一种效率较高的查找方法。

    【二分查找要求】:1.必须采用顺序存储结构 2.必须按关键字大小有序排列。

    【优缺点】折半查找法的优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。

    【算法思想】首先,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。

    重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。

    【算法复杂度】假设其数组长度为n,其算法复杂度为o(log(n))

    下面提供一段二分查找实现的伪代码:

    BinarySearch(max,min,des)

    mid-

    while(min<=max)

    mid=(min+max)/2

    if mid=des then

    return mid

    elseif mid >des then

    max=mid-1

    else

    min=mid+1

    return max

    折半查找法也称为二分查找法,它充分利用了元素间的次序关系,采用分治策略,可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是,将n个元素分成个数大致相同的两半,取a[n/2]与欲查找的x作比较,如果x=a[n/2]则找到x,算法终止。如 果xa[n/2],则我们只要在数组a的右 半部继续搜索x。

    Java的二分查找算法

    public class BinarySearch {

    /**

    * 二分查找算法

    *

    * @param srcArray 有序数组

    * @param des 查找元素

    * @return des的数组下标,没找到返回-1

    */

    public static int binarySearch(int[] srcArray, int des)

    {

    int low = 0;

    int high = srcArray.length-1;

    while(low <= high) {

    int middle = (low + high)/2;

    if(des == srcArray[middle]) {

    return middle;

    }else if(des

    high = middle – 1;

    }else {

    low = middle + 1;

    }

    }

    return -1;

    }

    public static void main(String[] args)

    {

    int[] src = new int[] {1, 3, 5, 7, 8, 9};

    System.out.println(binarySearch(src, 3));

    }

    }

    Java代码

    public class BSearch

    {

    public static int Max = 20;

    public static int[] Data = { 12, 16, 19, 22, 25, 32, 39, 48, 55, 57, 58,

    63, 68, 69, 70, 78, 84, 88, 90, 97 }; // 数据数组

    public static int Counter = 1; // 计数器

    public static void main(String args[])

    {

    int KeyValue = 22;

    // 调用折半查找

    if (BinarySearch((int) KeyValue))

    {

    // 输出查找次数

    System.out.println(“”);

    System.out.println(“Search Time = ” + (int) Counter);

    }

    else

    {

    // 输出没有找到数据

    System.out.println(“”);

    System.out.println(“No Found!!”);

    }

    }

    // —————————————————

    // 折半查找法

    // —————————————————

    public static boolean BinarySearch(int KeyValue)

    {

    int Left; // 左边界变量

    int Right; // 右边界变量

    int Middle; // 中位数变量

    Left = 0;

    Right = Max – 1;

    while (Left <= Right)

    {

    Middle = (Left + Right) / 2;

    if (KeyValue < Data[Middle]) // 欲查找值较小

    Right = Middle – 1; // 查找前半段

    // 欲查找值较大

    else if (KeyValue > Data[Middle])

    Left = Middle + 1; // 查找后半段

    // 查找到数据

    else if (KeyValue == Data[Middle])

    {

    System.out.println(“Data[" + Middle + "] = ” + Data[Middle]);

    return true;

    }

    Counter++;

    }

    return false;

    }

    }

    运行结果:

    Data[3] = 22

    Search Time = 5

    展开全文
  • 写出线性查找伪代码,它扫描整个序列来查找 v 。使用一个循环不变式来证明你的算法是正确的。确保你的循环不变式满足三条必要的性质。 以下是循环不变式的证明。 初始化:首先证明在第一次循环迭代之前(当 j ...

    考虑以下查找问题。

    输入:n个数的一个序列 A = <a1, a2, ... , an> 和一个值 v 。

    输出:下标 i 使得 v = A[i] 或者当 v 不在 A 中出现时,v 为特殊值 NIL 。

    写出线性查找的伪代码,它扫描整个序列来查找 v 。使用一个循环不变式来证明你的算法是正确的。确保你的循环不变式满足三条必要的性质。

    LINEAR-SEARCH(A, V):
        i = NIL
        j = 1
        while j <= A.length and i == NIL
            if A[j] = v
                i = j
            j = j + 1
        return i

    以下是循环不变式的证明。

    初始化:首先证明在第一次循环迭代之前(当 j = 1 时),循环不变式成立。这时子数组为空,由于子数组没有任何数据,即没有找到任何匹配 v 的下标 i,这时 i 为特殊值 NIL (已被初始化)成立。

    保持:其次处理第二条性质, for 循环体每次都会将 j 的下标迭代 1,由于数组 A[1..j-1] 没有找到 v (如果找到,循环早已因为 while 语句的 i != NIL 的条件判定结束)。那么只需要知道 A[j] 是否等于 v,即可知道 A[1..j] 是否存在 v。

    终止:最终算法会在 j = A.length + 1 或者 i != NIL 的情况下终止,考虑到不管是否能找到 v,由于每次迭代 j 都会增加1,所以最终循环必然能够终止。且当 j = A.length + 1 时,我们知道 A[1..j]已经被完整查找了一遍,如果找到了 v,则 i 为对应下标,如果没有找到 v,则 i 依然为初始值 NIL。另一方面,不管 j 是否为 A.length + 1,当 i 不为 NIL 时,说明我们已经在数组中找到了等于 v 的值的下标 i,循环终止。由此可知该算法是正确的。

    展开全文
  • 线性查找引言1、线性查找2、哨兵线性查找3、效率分析4、特点 引言 线性查找是顺序表或线性链表表示的静态查找表 ...【伪代码】——迭代法 def linear_search(A,x): n=len(A) answer = "NOT FOUND" for i

    引言

    • 线性查找是顺序表或线性链表表示的静态查找表
    • 表内元素无序
    • 线性查找又称为顺序查找

    1、思想

    \quad \quad 从表的一端开始,顺序扫描线性表,依次将扫描到的结点关键宇和给定值K相比较。若当前扫描到的结点关键字与K相等,则查找成功;若扫描结束后,仍未找到关键字等于K的结点,则查找失败。

    在这里插入图片描述

    2、算法

    2.1 线性查找

    【伪代码】——迭代法

    在这里插入图片描述

    def linear_search(A,x):
        n=len(A)
        answer = "NOT FOUND"
        for i in range(n):
            if A[i]==x:
                answer=i
        return answer
    

    【伪代码】——递归法

    在这里插入图片描述

    def Recursive_linear_search(A,i,x):# i:0
        n=len(A)
        if i>n:
            return "NOT-FOUND"
        else :
            if A[i]==x:
                return i
            else:
                return  Recursive_linear_search(A,i+1,x)   
    

    较好的线性查找

    (找到值就不再遍历,跳出循环)
    【伪代码】
    在这里插入图片描述

    def better_linear_search(A,x):
        n=len(A)
        for i in range(n):
            if A[i]==x:
                return i
        return print("NOT FOUND")
        
    

    2.2 哨兵线性查找

    \quad \quad 在上述线性查找中,每次循环都要比较两次:所在位置索引是否超过列表长度以及该值是否等于目标值。是否能改进?

    改进:
    \quad \quad
    把待查关键字Key存入表尾(称为“哨兵”、“监视哨”),从前往后逐个比较,可免去查找过程中每一步都要检测是否查找完毕,加快速度。

    【伪代码】
    在这里插入图片描述

    def sentinel_linear_search(A,x):
        n=len(A)
        last=A[n-1]#b保存数组最后一个元素
        A[n-1]=x#用x替换数组最后一个元素
        i=0
        while A[i]!=x:
            i+=1
        A[n-1]=last#还原数组最后一个元素
        if i<n-1 or A[n-1]==x:
            return i 
        else:
            print("NOT FOUND")
    
    

    3、查找性能(ASL)

    \quad \quad 假设列表长度为n,比较次数与关键字位置有关

    1、若查找成功

    \quad \quad 查找到表中第i个记录R[i-1]时,需比较i次,设表中记录查找概率相等,利用公式得平均查找长度:

    在这里插入图片描述
    2.若查找失败

    \quad \quad 每个元素都需要进行比较,故直接:

    ASL=n

    3、时间复杂度:

    \quad \quad 成功与失败的时间复杂度都为 O ( n ) O(n) O(n)

    4、空间复杂度:
    \quad \quad 一个辅助空间哨兵—— O ( 1 ) O(1) O(1)

    4、特点

    【优缺点】
    (1)优点:①算法简单②适用性广泛(对表的结构无任何要求)
    (2)缺点:查找效率低

    展开全文
  • 线性查找算法

    2017-03-21 17:02:03
    线性搜索的伪代码: 给定一个具有n个数的数组A,查找是否存在数x? linerSearch(A,x) k = 1 while k!=A[k] do k = k +1 if k>n then return 0 else return k 复杂度分析: 该算法在最好情形下的时间复杂度为Ω(1...
  • /*简单的拓扑排序伪代码*/ void Graph::topsort() {  for( int counter = 0; counter  {  vertex v = findNewVertexOfIndegreeZero();  if( v == NOT_A_VERTEX )  throw CycleFoundExcept
  • 伪代码: <strong><span style="font-size:14px;">Status ListInsert(SqList *L,int i,ElemType e) { int k; if(L->lenght==MAXSIZE) //顺序线性标已经满了 return ERROR; if(i||i>L->lengght+1) //当i...
  • 今天阅读了李航博士的《统计学习方法》第三章:k近邻分类方法,其中讲到kdTree的搜索时,没有特别弄清楚,遂在网上找到这样一篇文章,有详细的伪代码,理解轻松。 链接为:...
  • 二分搜索的伪码: 二分搜索的解题思路: a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8] 1 2 3 4 5 6 7 8 K=3 //输入8位数的数组 第一次查找: low=1 high=8 mid=(1+8)/2=4 (int整型舍去小数部分) K=3...
  • 线性查找问题

    2015-04-16 13:53:52
     写出线性查找伪代码它扫描整个序列来查找v。使用一个循环不变式来证明你的算法是正确的。确保你的循环不变式满足三条必要的性质。    BINART0ADD(A,B,C)  flag=0  for j  do  key  C[j]  
  • 2021年前端面试题及答案

    万次阅读 多人点赞 2020-02-11 19:29:34
    出现该状态代码时,浏览器能够自动访问新的URL,因此它是一个很有用的状态代码。注意这个状态代码有时候可以和301替换使用。例如,如果浏览器错误地请求http://host/~user(缺少了后面的斜杠),有的服务器返回301,...
  • 线性查找伪代码如下: 假定要查找的元素等可能的为数组中的任意元素,平均需要检查输入序列的元素个数为:。将该式子进行运算可得。 由此可得平均需要检测的输入序列元素个数为。 在最坏情况下,要查找的元素应...
  • 前端面试题(持续更新中)

    万次阅读 多人点赞 2019-11-06 17:16:33
    CSS3实现圆角(border-radius),阴影(box-shadow), 对文字加特效(text-shadow),线性渐变(gradient),旋转(transform) transform:rotate(9deg) scale(0.85,0.90) translate(0px,-30px) skew(-9deg,0deg);...
  • 前端面试题

    万次阅读 多人点赞 2019-08-08 11:49:01
    CSS3新增类有那些? 37 如何居中div,如何居中一个浮动元素? 38 浏览器的内核分别是什么?经常遇到的浏览器的兼容性有哪些?原因,解决方法是什么,常用hack的技巧 ? 39 列出display的值,说明他们的作用。...
  • 建立了一个单链表之后,假如要进行一些如插入、删除等操作该怎么办?...单链表的基本运算包括:查找、插入和删除。下面我们就一一介绍这三种基本运算的算法,并结合我们建立单链表的例子写出相应的程序。
  • 顺序表

    千次阅读 多人点赞 2019-11-06 08:49:33
    顾名思义,顺序表是物理地址连续的存储单元依次存储数据的线性结构,一般情况下采用数组存储,在数组上完成数据的增删查改。 顺序表和数组有什么区别呢? 顺序表比数组更约束,顺序表物理地址上必须连续存储,数组是...
  • 线性回归就是用一条直线去拟合所有的数据点,使得这些数据点拟合出来的误差最小。一般使用平方误差最小来作为标准去寻找线性回归的系数ws。用平方误差来作为标准是严格的数学证明的。 大概证明的思路是这样的,假设...
  • c代码实现哈希表线性探测再散列。关键字均为纯数字。查找时为单次查找,未加入循环
  • C#基础教程-c#实例教程,适合初学者

    万次阅读 多人点赞 2016-08-22 11:13:24
    CLR执行中间语言代码前,要对中间语言代码的安全性,完整性进行验证,防止病毒对中间语言代码的修改。  版本支持:系统中的组件或动态联接库可能要升级,由于这些组件或动态联接库都要在注册表中注册,由此可能...
  • 算法线性搜索 线性搜索算法 (Linear Search Algorithm) Linear search is a very basic and simple search algorithm. In Linear search, we search an element or value in a given array by traversing the array...
  • 考虑以下查找问题: 输入:n个数的一个序列A={ a1,a2, ..., an } 和一个值v。 输出:下标i使得v=A[i]或者当v不在A中时,v为特殊值NIL。...伪代码 cpp代码 #include using namespace std; int
  • 线性探测法的查找函数

    千次阅读 2019-06-22 23:19:11
    线性探测法:如遇到了冲突,用pos+i(i=1,2,3…)的方式来找到新的未用过的位置。 查找时,如果没有,我们的结束条件就时i>=表的长度。 这样缺点也很突出,就是很多元素会扎堆的出现,降低了效率,我们称为“一次...
  • 线性查找,也叫线性搜索: 我的理解就是在一个数组里面查找你想要的那个数字的下标,如果没有咱们以返回-1来表示; 思路: 遍历整个数组,一个for循环结束,输出所需要的下标 代码如下: #include <stdio.h...
  • 表和二叉树的排序,是利用元素之间的关系,逐个查找,或按一定的规律查找。 而散列表(哈希表),元素之间没有关系,它是利用了元素与存储地址之间的关系。 说白了,就是利用散列函数建立 元素->地址 的映射,然后...
  • 目录问题解析设计顺序查找算法核心伪代码二分查找算法核心伪代码分析源码 问题 使用两种检索算法求解有序数组中某元素的所在位置。 解析 有序数组最基本检索算法是顺序查找,又称线性查找,其思想是从数据结构...
  • 采用二分法查找时,数据需是排好序的。 基本思想:假设数据是按升序排序的,对于给定值key,从序列的中间位置k开始比较, 如果当前位置arr[k]值等于key,则查找成功; 若key小于当前位置值arr[k],则在数列的前半段...
  • 查找技术之线性表 图解和代码实现

    千次阅读 2013-03-12 23:37:39
    查找技术可从以下几个方面去讨论: 第一: 线性表的查找技术 第二:树表的查找技术 第三:散列表的查找技术     下面来讨论第一个:线性表的查找技术   1 顺序查找 1.1顺序表的顺序查找 基本思想:从...
  • 一、链地址法在等概率下查找成功和查找不成功的平均查找长度:将关键字序列{1 13 12 34 38 33 27 22} 散列存储到散列表中。散列函数为:H(key)=key mod 11,处理冲突采用链地址法,求在等概率下查找成功和查找不成功...
  • 【JAVA面试】java面试题整理(3)

    千次阅读 2018-10-28 12:50:13
    用来存放虚拟机加载的类信息,常量,静态变量,即时编译器编译后的代码等信息 GC会回收该区域的常量池和进行类型的卸载 *运行时常量池 ♣ Class文件的常量池用于存放编译期生成的各种字面量和符号引用,这部分...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 14,374
精华内容 5,749
关键字:

线性查找伪代码