线性搜索算法及其在C语言中的实现

1 年 ago

雅, 悟

2 minutes

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

在这个算法中，关键元素按顺序在给定的输入数组中进行搜索。

如果在输入数组中找到关键元素，则返回该元素。

线性搜索算法

线性搜索（数组X，值i）

Set j to 1
If j > n, jump to step 7
If X[j] == i, jump to step 6
Then, increment j by 1 i.e. j = j+1
Go back to step 2
Display the element i which is found at particular index i, then jump to step 8
Display element not found in the set of input elements.
Exit/End

线性搜索的伪代码

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语言中实现线性搜索。

Initially, we need to mention or accept the element to be searched from the user.
Then, we create a for loop and start searching for the element in a sequential fashion.
As soon as the compiler encounters a match i.e. array[element] == key value, return the element along with its position in the array.
If no values are found that match the input, it returns -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)。

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

结论

因此，在本文中，我们已经理解并实施了线性搜索算法。