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