线性搜索基本上是一种顺序搜索算法。

在此算法中，键元素在给定的输入数组中按顺序搜索。

如果在输入数组中找到key元素，它将返回该元素。

线性搜索算法

Linear_Search(数组X，值i)

• 将j设为1

• 如果j> n，则跳至步骤7

• 如果X [j] == i，则跳至步骤6

• 然后，将j递增1，即j = j + 1

• 返回步骤2

• 显示在特定索引i处找到的元素i，然后跳到步骤8

• 在输入元素集中找不到显示元素。

• 退出/结束

线性搜索的伪代码

procedure LINEAR_SEARCH (array, key)

 for each item in the array
    if match element == key
       return element's index
    end if
 end for

end procedure

C语言中线性搜索的实现

• 首先，我们需要提及或者接受用户要搜索的元素。

• 然后，我们创建一个for循环并开始按顺序搜索元素。

• 编译器遇到匹配项(即array [element] ==键值)后，立即返回元素及其在数组中的位置。

• 如果找不到与输入匹配的值，则返回-1。

线性搜寻

#include <stdio.h> 

int LINEAR_SEARCH(int inp_arr[], int size, int val) 
{ 
	 
	for (int i = 0; i < size; i++) 
		if (inp_arr[i] == val) 
			return i; 
	return -1; 
} 

int main(void) 
{ 
	int arr[] = { 10, 20, 30, 40, 50, 100, 0 }; 
	int key = 100; 
	int size = 10; 
	int res = LINEAR_SEARCH(arr, size, key); 
	if (res == -1)
	printf("ELEMENT NOT FOUND!!");
  else
  printf("Item is present at index %d", res);
  
	return 0; 
} 

输出：

Item is present at index 5

线性搜索的时间复杂度

如果在循环的第一次迭代中找到元素，则最佳情况下的复杂度为O(1)。

如果在数组的末尾找到搜索元素，则最坏情况下的时间复杂度为O(n)，前提是数组的大小为n。