线性搜索算法详解：C语言实现与代码示例

2 年 ago
雅, 悟
1 minute

线性搜索是一种基础的顺序搜索算法。在该算法中，目标元素会按照顺序在给定的输入数组中进行逐一查找。如果在输入数组中找到了目标元素，则返回该元素的位置信息。

线性搜索算法

线性搜索（数组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] == key值，就返回该元素及其在数组中的位置
  • 如果没有找到与输入匹配的值，则返回-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("未找到元素！！");
    else
    	printf("元素位于索引 %d 处", res);
    
	return 0; 
}

输出结果：

元素位于索引 5 处

线性搜索的时间复杂度

最佳情况时间复杂度：当元素在循环的第一次迭代中就被找到时，时间复杂度为O(1)。

最坏情况时间复杂度：当数组的大小为n且搜索元素位于数组末尾时，时间复杂度为O(n)。

平均情况时间复杂度：O(n)，因为平均需要检查一半的元素。

结论

综上所述，本文详细介绍了线性搜索算法的原理、实现方法及其时间复杂度分析。线性搜索虽然简单，但在小型数据集或未排序数据中仍然是一种实用的搜索方法。

bannerAds