Java順序查找算法詳解

更新時(shí)間：2022年08月03日 09:35:57 作者：Aricl.

順序查找又稱線性查找,主要用于在線性表中進(jìn)行查找。順序查找通常分為對(duì)一般的無序線性表的順序查找和對(duì)按關(guān)鍵字有序的順序表的順序查找，下面我們來一探究竟

一、查找的基本概念

在講順序查找法之前先來認(rèn)識(shí)一些關(guān)于查找的基本概念。

1.查找表

由同一類型的數(shù)據(jù)元素（或記錄）所構(gòu)成的集合
數(shù)據(jù)元素之間存在完全松散的關(guān)系
非常靈活的數(shù)據(jù)結(jié)構(gòu)

2.關(guān)鍵字

關(guān)鍵字是數(shù)據(jù)元素（或記錄）中某個(gè)數(shù)據(jù)項(xiàng)的值，可以用它標(biāo)識(shí)一個(gè)數(shù)據(jù)元素（或記錄）
若關(guān)鍵字可以唯一地標(biāo)識(shí)一個(gè)記錄，則稱之為主關(guān)鍵字
反之，若用以識(shí)別若干記錄的關(guān)鍵字稱之為次關(guān)鍵字
注意，當(dāng)元素只有一個(gè)數(shù)據(jù)項(xiàng)時(shí)，其關(guān)鍵字即為該數(shù)據(jù)元素的值

3.查找

查找是根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)關(guān)鍵字等于給定值的記錄或者數(shù)據(jù)元素
若表中存在該記錄則查找成功，可返回整個(gè)記錄的信息或者指示該記錄在查找表中的位置
若表中不存在該記錄則查找失敗，可返回一個(gè)“空”記錄或者“空”指針

4.動(dòng)態(tài)查找表與靜態(tài)查找表

若在查找的過程中對(duì)表做修改操作（如插入或刪除），則相應(yīng)的表稱之為動(dòng)態(tài)查找表，否則為靜態(tài)查找表
即動(dòng)態(tài)查找表的表結(jié)構(gòu)本身是在查找的過程中所動(dòng)態(tài)生成的，即在創(chuàng)建表時(shí)，對(duì)于給定值，若表中存在其關(guān)鍵字所對(duì)應(yīng)的記錄，則查找成功返回；否則插入關(guān)鍵字等于給定值的記錄

5.平均查找長(zhǎng)度

為確定記錄在查找表中的位置，需要和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的期望值，稱為查找算法在查找成功時(shí)的平均查找長(zhǎng)度（Average Searche Length, ASL）
由于查找算法的基本運(yùn)算是關(guān)鍵字之間的比較操作，故可以使用ASL來衡量評(píng)估查找算法的性能
也可以采用一種很直觀的評(píng)估方法——程序執(zhí)行所消耗的時(shí)間。文章傳送門

二、順序查找法

1.概念

順序查找（Sequential Search）的查找過程為：從表的一端開始，依次將記錄的關(guān)鍵字和給定的值進(jìn)行比較，若某記錄的關(guān)鍵字和給定值相等，則為查找成功；反之，若掃描整個(gè)表之后，仍然未找到關(guān)鍵字和給定值相等的記錄，則為查找失敗。

2.實(shí)踐

在給定的無序數(shù)組中查找給定的值

public class DayOne {
    public static void main(String[] args) {
        int []a={8,7,45,99,65,23,21,100};
        int key1=23;
        int key2=666;
        DayOne dayone=new DayOne();
        System.out.print("數(shù)組元素：");
        for(int i=0;i<a.length;i++){
            System.out.print(a[i]+" ");
        }
        System.out.println();
        System.out.println("查找key1的結(jié)果："+dayone.search(a,key1));
        System.out.println("查找key2的結(jié)果："+dayone.search(a,key2));
    }
    public  String search(int []a,int key){
        //初始化變量
        int i=0;
        //掃描整個(gè)數(shù)組
        while(i<a.length){
            //將數(shù)組元素一一與給定值key進(jìn)行比較
            if(key==a[i])
                return "查找成功！ "+key+"是數(shù)組的第"+(i+1)+"個(gè)元素";//匹配成功則返回
            i++;//當(dāng)前未匹配成功將索引下標(biāo)i后移一位繼續(xù)比對(duì)
        }
        //如果循環(huán)遍歷已經(jīng)結(jié)束了還未找到給定值key則表明數(shù)組中不存在該值，查找失敗
        return "查找失敗，數(shù)組中不存在該元素！";
    }
}

執(zhí)行結(jié)果