搜索是在列表中查找某个特定元素的过程。 如果元素存在于列表中，则该过程称为成功，并且该过程返回该元素的位置，否则搜索将被称为不成功。
有两种流行的搜索方法被广泛用于在列表中搜索某些项目。 但是，算法的选择取决于列表的排列。
- 线性搜索
- 二进制搜索
线性搜索
线性搜索是最简单的搜索算法，通常称为顺序搜索。 在这种类型的搜索中，只是完全遍历列表，并将列表中的每个元素与要找到其位置的项匹配。如果找到匹配，则返回项目的位置，否则算法返回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
