数据结构与算法-顺序查找

女爷i 2022-04-10 03:19 389阅读 0赞

### 概要 ###

*   *   *  查找概论
         *  顺序查找基本概念
         *  java代码实现
         *  时间复杂度分析

### 查找概论 ###

> 只要你打开电脑，就会涉及查找技术。如炒股软件中查找股票信息、硬盘文件中找照片等，都要涉及到查找。当然，在互联网上查找信息就更加是家常便饭。所有这些需要被查数据所在的集合，我们给它一个统称叫*查找表*。  
> **查找表（Search Table）是由同一类型的数据元素（或记录）构成的集合**。查找表按照操作方式分为*静态查找表*和*动态查找表*。**静态查找表只作查询操作，即查询某个“特定的”数据元素是否在查找表中或者检索某个“特定的”数据元素和各种属性**；**动态查找表在查找过程中同时插入表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。**  
> **关键字（Key）是数据元素中某个数据项的值**，又称键值，用它可以标识一个数据元素。**若此关键字可以唯一地标识一个记录，则称此关键字为主关键字（Primary Key）**；**对于那些可以识别多个数据元素（或记录）的关键字，我们称之为次关键字（Secondary Key）**。  
> **查找（Searching）就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。**

### 顺序查找基本概念 ###

> 顺序查找（Sequential Search）又叫线性查找，是最基本的查找技术，它的查找过程是：从表中第一个（或者最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果直到最后一个（或第一个）记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功。

### java代码实现 ###

/**
     * 顺序查找
     * 
     * @param a	查找表
     * @param key	给定值
     * @return	目标记录在查找表中的位置
     */
    Integer sequential_search(int[] a, int key) {
        
    	for (int i = 0; i < a.length; i++) {
        
    	     if (key == a[i]) {
        
    		 return i;
    	     }
    	}
    	return null;
    }
    
    //声明查找表
    int[] a = {
        3,1,9,2};
    
    //测试调用		
    sequential_search(a, 9);  //输出2
    sequential_search(a, 99); //输出null

### 时间复杂度分析 ###

*  查找成功最好的情况就是在第一个位置就找到了，算法时间复杂度为0(1)，最坏的情况是在最后一位置才找到，需要n次比较，时间复杂为0(n)。
 *  当查找不成功时，需要n次比较，时间复杂度为0(n)。
 *  由于关键字在任何一位置的概率是相同的，所以平均查找次数为n/2，所以最终时间复杂度为O(n)。