線性搜尋


搜尋是在列表中查詢某個特定元素的過程。 如果元素存在於列表中,則該過程稱為成功,並且該過程返回該元素的位置,否則搜尋將被稱為不成功。

有兩種流行的搜尋方法被廣泛用於在列表中搜尋某些專案。 但是,演算法的選擇取決於列表的排列。

  • 線性搜尋
  • 二進位制搜尋

線性搜尋

線性搜尋是最簡單的搜尋演算法,通常稱為順序搜尋。 在這種型別的搜尋中,只是完全遍歷列表,並將列表中的每個元素與要找到其位置的項匹配。如果找到匹配,則返回專案的位置,否則演算法返回NULL
線性搜尋主要用於搜尋未排序專案的無序列表。 線性搜尋演算法如下。

LINEAR_SEARCH(A,N,VAL)
第1步:[INITIALIZE] SET POS = -1
第2步:[INITIALIZE] SET I = 1
第3步:當I <= N 時重複第4步
第4步:如果 A [I] = VAL
    SET POS = I
    列印POS
    轉到第6步
    [IF結束]
    SET I = I + 1
    [迴圈結束]
第5步:IF POS = -1
    列印「值不在陣列中」
    [IF結束]
第6步:退出

演算法的複雜性

複雜度 最好情況 平均情況 最壞情況
時間 O(1) O(n) O(n)
空間 O(1)

以下是幾種語言的程式碼實現。

C語言實現程式碼 -

#include<stdio.h>   
void main ()  
{  
    int a[10] = {10, 23, 40, 1, 2, 0, 14, 13, 50, 9};  
    int item, i,flag;  
    printf("Enter Item which is to be searched\n");  
    scanf("%d",&item);  
    for (i = 0; i< 10; i++)  
    {  
        if(a[i] == item)   
        {  
            flag = i+1;  
            break;  
        }   
        else   
        flag = 0;  
    }   
    if(flag != 0)  
    {  
        printf("Item found at location %d\n",flag);  
    }  
    else  
    {  
        printf("Item not found\n");   
    }  
}

執行上面範例程式碼,得到的輸出結果如下 -

Enter Item which is to be searched
20
Item not found
Enter Item which is to be searched
23
Item found at location 2

Java語言實現程式碼 -

import java.util.Scanner;  

public class Leniear_Search {  
public static void main(String[] args) {  
    int[] arr = {10, 23, 15, 8, 4, 3, 25, 30, 34, 2, 19};  
    int item,flag=0;   
    Scanner sc = new Scanner(System.in);  
    System.out.println("Enter Item ?");  
    item = sc.nextInt();  
    for(int i = 0; i<10; i++)  
    {  
        if(arr[i]==item)  
        {  
            flag = i+1;  
            break;  
        }  
        else   
            flag = 0;   
    }  
    if(flag != 0)  
    {  
        System.out.println("Item found at location" + flag);  
    }  
    else   
        System.out.println("Item not found");  

   }  
}

執行上面範例程式碼,得到以下結果:

Enter Item ?
23
Item found at location 2
Enter Item ?
22
Item not found

C#語言實現程式碼 -

using System;  

public class LinearSearch  
{  
    public static void Main()  
    {  
        int item, flag = 0;  
        int[]  a= {10, 23, 5, 90, 89, 34, 12, 34, 1, 78};   
        Console.WriteLine("Enter the item value");  
        item = Convert.ToInt32(Console.ReadLine());  
        for(int i=0;i<10;i++)  
        {  
            if(item == a[i])  
            {  
                flag = i+1;  
                break;  
            }  
            else   
                flag = 0;   
        }  
        if(flag != 0 )   
        {  
            Console.WriteLine("Item Found at Location " + flag);  
        }  
        else   
            Console.WriteLine("Item Not Found");  

    }  
}

執行上面範例程式碼,得到以下結果:

Enter the item value
78
Item Found at Location 10

Enter the item value 
22
Item not found

Python語言實現程式碼 -

arr = [10,2,3,4,23,5,21,45,90,100];  
item = int(input("Enter the item which you want to search "));  
for i in range (0,len(arr)):  
    if arr[i] == item:  
        flag = i+1;  
        break;  
    else:   
        flag = 0;   
if flag != 0:   
    print("Item found at location %d" % (flag));  
else :   
    print("Item not found");

執行上面範例程式碼,得到以下結果:

Enter the item which you want to search 2
Item found at location 2
Enter the item which you want to search 101 
Item not found