用Python编写线性搜索程序

线性搜索是一种从数组中搜索某些特定值的搜索技术。这是最简单的搜索技术。

在这种搜索技术中，

• 将要搜索的值与数组中的所有元素进行比较。

• 如果找到该值，则返回该元素的索引。

• 如果特定元素不存在于整个数组中，则返回-1或一些相关的字符串消息。

伪码

linearSearch(int array[], int value):
   for i=0 to len(array):
      if(array[i]==value):
         Element is Present
   //外循环
   Element Not Present // element not found in the whole array

例子

def linearSearch(arr,value):
   for i in range(len(arr)):
      if(arr[i]==value):
         return i
   return -1
array=[1,2,3,4,5,6,7,8,9,10]
value=5
a=linearSearch(array,value)
if(a==-1):
   print("Element not present")
else:
   print("Element present at index",a)

输出

Element present at index 4

时间复杂度

线性搜索的最坏情况时间复杂度为O(n)。当元素出现在数组的最后一个索引处或根本不存在时，会发生最坏的情况。

线性搜索的最佳情况下时间复杂度为O(1)。最好的情况是元素出现在数组的第一个索引处。

改进的线性搜索

线性搜索的最坏情况复杂度可以提高到O（n / 2）。可以使用左右两个指针同时进行两次比较来完成此操作，从而将线性搜索的最坏情况下的时间复杂度降低到O（n / 2）。

例子

def linearSearch(arr,value):
   left=0
   right=len(arr)-1
   while(left<=right):
      if(arr[left]==value):
         return left
      elif(arr[right]==value):
         return right
      left+=1
      right-=1
   return -1
array=[1,2,3,4,5,6,7,8,9,10]
value=10
a=linearSearch(array,value)
if(a==-1):
   print("Element not present")
else:
   print("Element present at index",a)

输出

Element present at index 9

在上面的示例中，出现在最后一个索引处的元素是在第一次迭代本身中找到的。使用第一种方法，将需要10次迭代才能找到此元素。

如果未找到该元素，则最坏情况的复杂度为O（n / 2），因为第二种方法的迭代总数为n / 2。

线性搜索有多有用？

线性搜索很少使用，因为有更好的搜索算法（例如二进制搜索）可以提供更好的时间复杂度。对于大型输入数组，线性搜索效率不高。