精华内容
参与话题
问答
  • 一、顺序查找:顾名思义,就是从头开始一直找到结束,找到了就返回,否则继续找,找完了没找到就返回-1 普通版 static int SequenceFind(int[] arr,int value) { for (int i = 0; i < arr.Length-1; i++) { if...

    顺序查找也称线性搜索(Linear Search),是在一个已知无(或有序)序队列中找出与给定关键字相同的值的具体位置。原理是让关键字与队列中的第1个(或最后1个)位置的值逐个比较,直到找出与给定关键字相同的值为止,它的缺点是效率低下。

    示例

    public class Program {
    
        public static void Main(string[] args) {
            int[] array = { 43, 69, 11, 72, 28, 21, 56, 80, 48, 94, 32, 8 };
    
            Console.WriteLine(SequentialSearch(array, 80));
    
            Console.ReadKey();
        }
    
        private static int SequentialSearch(int[] array, int key) {
            for (int i = 0; i < array.Length; i++)
                if (array[i] == key)
                    return i;
            return -1;
        }
    
    }
    

    在最坏的情况下时间复杂度为: O(n) 。

    展开全文
  • import java.util.Scanner; ... * 顺序查找算法 * * @author Administrator * */ public class SearchFun { final static int N = 15; // 顺序查找算法实现 public static in...
    
    
    package com.xj.www.search;
    import java.util.Scanner;
    /**
     * 顺序查找算法
     *
     * @author xiongjing
     *
     */
    public class SearchFun {
          final static int N = 15;
          // 顺序查找算法实现
          public static int search(int[] a, int n, int x) {
                int i, f = -1;
                for (i = 0; i < n; i++) {
                      if (x == a[i]) {
                            f = i;
                            break;
                      }
                }
                return f;
          }
          // 程序主入口
          public static void main(String[] args) {
                int x, n, i;
                int[] shuzu = new int[N];
                for (i = 0; i < N; i++) {
                      shuzu[i] = (int) (100 + Math.random() * (100 + 1));
                }
                System.out.print("顺序查找算法演示! \n");
                System.out.println("数据序列: \n");
                for (i = 0; i < N; i++) {
                      System.out.print(" " + shuzu[i]);
                }
                System.out.print("\n\n");
                System.out.println("请输入要查找的数:");
                @SuppressWarnings("resource")
                Scanner input = new Scanner(System.in);
                x = input.nextInt();
                n = search(shuzu, N, x);
                if (n < 0) {
                      System.out.println("没找到数据:" + x);
                } else {
                      System.out.println("数据:" + x + "位于数组的第" + (n + 1) + "个元素处。");
                }
          }
    }
    
    
    展开全文
  • 查找算法顺序查找

    千次阅读 2020-02-20 15:30:28
    学到这里,相信大家对基本的数据结构都有了一定的认识,当然,我们还有一些...本篇文章将介绍顺序查找算法。 文章目录何为顺序查找?算法改进时间效率分析 何为顺序查找? 看到这个算法的名字不难理解,它是一种按...

    学到这里,相信大家对基本的数据结构都有了一定的认识,当然,我们还有一些数据结构没有讲解,比如:图、广义表、数组等。这些内容我都会在后续进行更新。

    不过这段时间,我主要还是先介绍一下查找和排序算法,在这些算法中如果涉及到还未介绍的数据结构,我就会对该数据结构进行介绍。

    本篇文章将介绍顺序查找算法。

    何为顺序查找?

    看到这个算法的名字不难理解,它是一种按照序列原有顺序对数组进行遍历比较查询的基本查找算法。

    该算法其实非常简单,大家肯定都会写,若是想查找一个序列中的某个元素值,我们只需遍历该序列,依次与序列中的每一个元素进行比较即可。

    先来构造一个查找表:

    #include <stdio.h>
    #include <malloc.h>
    
    #define LENGTH 10
    
    typedef struct{
    	int key;	//数据域
    	//...还可以指定数据的其它信息
    }ElemType;
    
    typedef struct{
    	ElemType *elem;
    	int length;
    }SSTable;
    
    SSTable CreateTable(){
    	SSTable st;
    	st.length = LENGTH;
    	st.elem = (ElemType*) malloc(sizeof(ElemType) * (LENGTH + 1));
    
    	//为元素赋值
    	st.elem[1].key = 1;
    	st.elem[2].key = 2;
    	st.elem[3].key = 3;
    	st.elem[4].key = 4;
    	st.elem[5].key = 5;
    	st.elem[6].key = 6;
    	st.elem[7].key = 7;
    	st.elem[8].key = 8;
    	st.elem[9].key = 9;
    	st.elem[10].key = 10;
    
    	return st;
    }
    

    数组的元素值我就直接写死了,大家也可以利用循环来自己输入。

    对于初学者,这里的很多地方他们可能会有些疑惑,比如:为什么在申请内存的时候要多申请一个空间;在为数组赋值的时候为什么从下标为1的位置开始,这些我都放到后面解释。

    先来看看查找算法的实现:

    //顺序查找算法
    int SequentialSearch(SSTable st,int key){
    	int i;
    	for(i = 1;i <= st.length;++i){
    		if(st.elem[i].key == key){
    			return i;
    		}
    	}
    	return 0;
    }
    

    算法非常简单,遍历依次比较即可,若找到则直接返回当前下标;若没找到,则返回0。

    算法改进

    刚才虽然实现了顺序查找算法,但有些欠缺,因为每次循环都需要进行两次比较:比较下标是否越界;比较当前值是否等于待查找值。

    当数据量非常庞大的时候,显然效率就比较低下了,那么有没有一种办法能够让它只比较一次就能够实现查找呢?这就是刚才为什么要多申请一个内存空间的原因了。

    原数组中共有10个有效元素,但是在申请空间时要去申请11个内存空间,并且赋值要从下标为1的位置开始,目的就是空出下标为0的位置,如下图:
    在这里插入图片描述
    空出这个位置做什么呢?做一个监视哨,即:这个下标为0的位置要起一个哨兵的作用,举个例子:

    我现在要查找值为8的元素,那么在查找开始之前,我先将元素值8放入下标为0的位置作为哨兵:
    在这里插入图片描述
    此时查找就很容易了,同样地,先遍历序列,但是无需比较下标是否越界了,我们直接让当前元素值与哨兵进行比较,若找到,则返回当前下标;
    若当前序列中没有哨兵位置的元素值,则从下标为1开始到最后一个元素都将找不到待查找元素,此时一定会在哨兵位置找到,这个时候也直接返回当前下标即可,0则代表未找到。

    带哨兵的顺序查找算法实现如下:

    //带哨兵的顺序查找算法
    int SequentialSearch(SSTable st,int key){
    	int i;
    	//设置哨兵
    	st.elem[0].key = key;
    	for(i = st.length;st.elem[i].key != key;--i);
    	return i;
    }
    

    记得从数组最后一个元素开始遍历,这样如果在哨兵位置遍历结束,就证明查找失败。

    时间效率分析

    下面来分析一下带哨兵的顺序查找算法的时间效率。

    在这里插入图片描述
    若要在该序列中查找值为10的元素,则只需进行一次比较就查找到了;
    若要在该序列中查找值为9的元素,则需进行两次比较才能找到,以此类推。

    查找次数是受查找的值影响的,若要查找第i个元素,则需比较length + 1 - i次;查找失败则需比较length + 1次。

    假设表中各记录的查找概率相同,则其查找的平均查找长度为:
    ASLs=(1+2+...+length)/length=(n+1)/2ASL_s = (1 + 2 + ... + length) / length = (n + 1) / 2
    则其时间复杂度为O(n)。

    顺序查找算法的优点是:

    算法简单,逻辑次序无要求,且不同存储结构均适用

    缺点:

    平均查找长度太长,时间效率太低

    展开全文
  • 【算法分析】查找算法:二分查找、顺序查找

    万次阅读 多人点赞 2012-07-19 09:51:07
    08年9月入学,12年7月毕业,结束了我在软件学院愉快丰富的大学生活。...查找算法是在存在的序列(list) 中查找特定的目标(target),要求序列中每个记录必须与一个关键词(key)关联才能进行查找。

    08年9月入学,12年7月毕业,结束了我在软件学院愉快丰富的大学生活。此系列是对四年专业课程学习的回顾,索引参见:http://blog.csdn.net/xiaowei_cqu/article/details/7747205


    查找算法


    查找算法是在存在的序列(list) 中查找特定的目标(target),要求序列中每个记录必须与一个关键词(key)关联才能进行查找。

     
    查找算法通常需要两个输入:
    1、被查找的序列
    2、要查找的关键词
    查找算法的输出参数和返回值:
    1、返回类型为 Error_code 的值用以表示是否查找成功
    2、如果查找成功,返回 success, 输出参数 position 定位到目标所在位置
    3、如果查找失败,返回 not present,输出参数可能是未定义或不同于已有位置的任何值

    顺序查找算法


    顺序查找算法的思路很简单:从表的第一个元素开始一个一个向下查找,如果有和目标一致的元素,查找成功;如果到最后一个元素仍没有目标元素,则查找失败。

    【实验说明】

    题目:编写一个程序,对顺序表{3,6,2,10,1,8,5,7,4,9},采用顺序查找关键字5的过程。要求输出:
    1)原顺序表;2)查找到关键字的位置;3)进行比较的次数。
    1.首先要编写类表List。需要满足最基本的操作插入insert(),获取retrieve(),以及得到大小size()。
    2.我们观察题目要求,表中虽然存储的是简单的整数,但如果我们使用List<int>对象显然无法记录比较次数,所以我们自己写一个类Key通过其内部int类型的数据成员来记录存于表中的值,并模仿int基本的逻辑操作,即编写重载逻辑运算符,同时增加一个静态数据成员comparisons用于记录其比较操作的次数。
    3.准备工作做好之后开始编写顺序查找算法。算法的思路很简单,也较易实现,从表中第一个元素开始比较,发现目标则返回元素所在表中位置;若遍历之后没有目标,则查找失败,返回-1表示表中没有目标元素。
    4.按题目要求编写最后的输出函数。

    【相关代码】

    函数 sequential_search
    int sequential_search(const List<int> &the_list,
    					  const Key &target)
    /*Post: If an entry in the_list is equal to target, then return the position
            of this entry. 
    		Otherwise return -1 
    */
    {
    	int position;
    	int s=the_list.size();
    	for(position=0;position<s;position++){
    		int data;
    		the_list.retrieve(position,data);
    		if(data==target){
    			return position;
    		}
    	}
    	return -1;
    }
    

    二分查找算法


    二分查找前提是表是按递增或递减顺序的规范表。此次实验中我们使用的是递增表。
    二分查找从表中间开始查找目标元素。如果找到一致元素,则查找成功。如果中间元素比目标元素小,则仍用二分查找方法查找表的后半部分(表是递增排列的),反之中间元素比目标元素大,则查找表的前半部分。

    【实验说明】

    题目:编写一个程序,对有序表{1,2,3,4,5,6,7,8,9,10},采用二分查找关键字9的过程。要求输出:
    1)原顺序表;2)查找到关键字的位置;3)进行比较的次数。
    1.二分查找算法的前提是表必须是有序的,如题目中是递增方式排列的表。实现表的有序一方面是用户规范输入,另一方面我们也可以编写有序的类来方便用户的输入。
    所以从List中派生类Oredered_list,重新编写函数Error_code insert(int position,const Record &data),使插入的位置不满足表的有序条件时,不能插入。
    同时编写插入的重载函数 Error_code insert(const Record &data),可以直接插入到合适的位置,方便用户输入。
    2.仍使用题目1中的Key来表示目标
    3.实现二分查找算法。通过书中的学习,我们直接使用添加相等判断的二分查找算法。即每次从表的中间元素开始比较,如果得到目标则返回元素所在表中位置;如果中间元素小于目标元素,则对右半部分继续二分查找;反之对前半部分表进行二分查找。若最后都没有目标元素,返回-1用以表示表中没有目标元素。
    4.仍使用题目1编写的输出函数将结果输出。
    /*注意这里因为Ordered_list是从List中派生而来,所以虽然print_out函数中第一个参数类型是List<int>,仍可以使用,而不用编写重载函数*/

    【相关代码】

    函数 binary_search
    int binary_search(const Ordered_list<int> &the_list,
    					const Key &target)
    /*Post: If an entry in the_list is equal to target, then return the position
            of this entry. 
    		Otherwise return -1 
    */
    {
    	int position;
    	int data;
    	int bottom=0,top=the_list.size()-1;
    	while(bottom<=top){
    		position=(bottom+top)>>1; 
    		the_list.retrieve(position,data);
    		if(data==target)
    			return position;
    		if(data<target)bottom=position+1;
    		else top=position-1;
    	}
    	return -1;
    }

    【过程记录】

    实验截图:


    【结果分析】


    A.实现顺序查找算法

    1.顺序查找算法思路很简单,就是一种遍历的思想,一个个查找目标元素,实现也很简单。
    2.对于有n个元素的表适用顺序查找。比较次数:不成功:比较n次。成功查找:最好的情况为1次,即第一个元素即为目标元素;最差的情况为n次;平均比较次数(n+1)/2次。
    所以当表很大时,顺序查找的代价是很大的。
    3.顺序查找算法不会有重复的比较出现,即一旦找到即成功,但同时这种代价是当表中有重复的目标元素时(比如有多个目标元素)我们只能得到第一个元素的位置。

    B.实现二分查找算法

    1.二分查找法思路:递增排列的表,首先从中间元素开始查找,如果元素比目标元素小,则查找后半部分表,反之查找前半部分表,并重复这一过程。这样每次查找中我们都把表的长度减半。
    2.二分查找在实现中有量bottom和top,每次减半的过程体现在bottom和top的改变上,在代码的实现上可以使用单纯的循环或者用函数递归的思想。
    递归思想更容易理解,但编写之后我们发现函数是尾递归,尾递归通常可以用简单的循环实现,循环在操作来说没有了函数调用的过程,更节省时间和空间。
    3.编码中小小地方的改动可能对程序有很大的改观。
    如上述两种二分查找binary_search_1(不比较等于的情况)binary_search_2(添加等于情况)



    实验代码下载:http://download.csdn.net/detail/xiaowei_cqu/4437702

    (转载请注明作者和出处:http://blog.csdn.net/xiaowei_cqu 未经允许请勿用于商业用途)



    展开全文
  • 顺序查找算法

    2019-05-23 16:01:23
    //顺序查找算法 // a) 原理:顺序查找就是按顺序从头到尾依次往下查找,找到数据, // 则提前结束查找,找不到便一直查找下去,直到数据最后一位。 // b) 图例说明: 原始数据:int[] a={4,6,2,8,1,9,0,3}; 要...
  • 查找算法--顺序查找

    2018-06-23 10:13:52
    数据结构用C++的实现,蓝桥杯,ACM,算法基础,C++入门
  • 顺序查找:就是从一个集合的第一个元素开始遍历,一直到找到队尾为止,返回查找的下标,因此遍历的结果为:可能找到元素,返回元素下标,可能遍历到队尾仍然找不到元素... * 顺序查找算法  * @author gaojingsong...
  • 查找算法:二分查找、顺序查找的实现 参见博客:http://blog.csdn.net/xiaowei_cqu/article/details/7748260
  • 顺序查找
  • 查找算法顺序查找

    2016-12-01 21:44:32
    查找算法顺序查找
  • 查找算法_顺序查找

    2013-10-02 20:42:03
    顺序查找又称为线性查找,是最基本的查找技术之一,基本思想是:从线性表的一端向另一端逐个将关键字与给定的值进行比较,若相等,则查找成功,给出该记录的位置,若整个表查找完也没找到,则返回查找失败。...
  • 算法Algorithm 一个计算过程,解决问题的方法 递归: 调用自身 结束条件 时间复杂度: 用来估计算法运行时间的一个式子 O(1) &amp;lt; O(logn) &amp;lt; O(n) &amp;lt; O(nlogn) &amp;lt; ...
  • 顺序查找算法和二分查找算法

    千次阅读 2015-01-11 23:32:50
    顺序查找算法和二分查找算法
  • 查找算法是程序设计处理非数值问题非常重要的操作。查找算法包括:基于线性表的查找,基于树的查找,哈希表查找。 基于线性表的查找包括顺序查找、折半查找,和分块查找。 【顺序查找顺序查找是指从表的一端...
  • 查找算法-顺序查找、有序查找

    千次阅读 2016-12-06 16:15:44
    1)顺序查找 顺序查找又称为线性查找,是一种最简单的查找方法。  从表的一端开始,向另一端逐个按要查找的值key 与关键码key进行比较,若找到,查找成功,并给出数据元素在表中的位置;若整个表检测完,仍未...
  • //顺序查找算法 #include <stdio.h> int search(int arr[],int key){ int i; for(i=9;i>=0;i--) if(arr[i]==key) return i; } int main(){ int a[10]; int i; for(i=1;i<10;i++) a[i]=i;//1...
  • 查找算法-顺序查找和折半查找

    千次阅读 2018-03-15 15:25:13
    顺序查找 遍历数组的每一个元素,线性查找,时间复杂度为O(n). 代码 class Solution: def GetNumberOfK(self, data, k): length=0 for i in range(len(data)): if data[i]==k: return k ...
  • 顺序查找又称为线性查找,是一种最简单、最基本的查找方法。 顺序查找的基本思想是从顺序表的一端开始,依次将每一个数据元素的值与关键字值key比较,若相等,则表明查找成功;若直到所有元素都比较完毕仍找不到,...

空空如也

1 2 3 4 5 ... 20
收藏数 29,931
精华内容 11,972
关键字:

顺序查找