搜索数组中的元素的Python程序

在Python中，主要使用两种搜索算法。其中，第一种是线性搜索，第二种是二分搜索。

这两种技术主要用于从给定的数组或列表中搜索元素。在搜索元素时，可以遵循任何一种算法的两种方法论。其中之一是递归方法，另一种是迭代方法。让我们讨论两种算法的两种方法论并解决类似的问题。

线性搜索

线性搜索技术也称为顺序搜索。该名称“顺序搜索”的含义定义了该搜索算法所遵循的过程。这是一种在Python中用于查找数组或列表中元素的方法或技术。

它被认为是所有其他搜索算法中最简单，最容易的方法。但是，该算法的唯一缺点是效率不高。这就是不经常使用线性搜索的主要原因。

算法

• 步骤1 − 它通过将所需元素与给定数组中存在的每个元素进行比较以顺序方式搜索元素。

• 步骤2 − 如果找到所需元素，则向用户显示元素的索引或位置。

• 步骤3 − 如果元素不存在于数组中，则会通知用户未找到该元素。以这种方式处理算法。

通常，线性搜索算法适用于大小小于或等于100的小数组或小列表，因为它检查并与每个元素进行比较。

• 如果所需元素位于数组的最后位置，则需要更长的时间。

• 线性搜索算法在最佳情况下的时间复杂度为“O（1）”。在这种情况下，元素将位于数组的第一个位置，即索引为“0”。

• 线性搜索算法在平均情况下的时间复杂度为“O（n）”。在这种情况下，该元素将位于数组的中间位置，即索引为“（n-1）/ 2”或“（（n-1）/ 2）+ 1”。

• 线性搜索算法在最坏情况下的时间复杂度为“O（n）”。在这种情况下，元素将位于数组的最后位置，即索引为“n-1”。

例子

在以下示例中，我们将了解使用线性搜索在数组中搜索元素的过程。

def iterative_linear( arr, n, key_element):
   for x in range(n):
      if(arr[x] == key_element):
         return x
   return -1
arr = [2, 3, 5, 7, 9, 1, 4, 6, 8, 10]
max_size = len(arr)
key = 8
result = iterative_linear(arr, max_size - 1, key)
if result != -1:
   print ("元素", key,"在索引",(result),"和",(result+1),"位置上找到")
else:
   print ("给定的数组中没有此元素%d" %(key))

结果

上面程序的输出如下−

元素8在索引8和9位置上找到

例子（递归）

在以下示例中，我们将学习使用递归方法中的线性搜索在数组中搜索元素的过程。

def recursive_linear( arr, first_index, last_index, key_element):
   if last_index < first_index:
      return -1
   if arr[first_index] == key_element:
      return first_index
   if arr[last_index] == key_element:
      return last_index  
   return recursive_linear(arr, first_index + 1, last_index - 1, key_element)

arr = [2, 3, 5, 7, 9, 1, 4, 6, 8, 10]
max_size = len(arr)
key = 8
result = recursive_linear(arr, 0, max_size - 1, key)
if result != -1:
   print ("元素", key, "在索引", result, "和位置", result+1, "处找到")
else:
   print ("给定的数组中没有元素 %d" %(key))

输出

上述程序的输出如下 −

元素 8 在索引 8 和位置 9 处找到

二分查找

二分查找算法与线性查找算法完全不同。它遵循完全不同的过程来从数组中查找元素。通常只考虑有序数组。

在某些情况下，如果数组没有排序，则对数组进行排序，然后开始二分查找算法的过程。一旦二分查找算法考虑到数组，它首先对数组进行排序，然后将算法应用于该数组。

算法

• 步骤1 − 首先对数组进行排序。

• 步骤2 − 排序后，将数组视为两个部分。 一半是从已排序的数组的第一个元素到中间元素开头，另一半是从中间元素的后一个元素到已排序的数组的最后一个元素开头。

• 步骤3 − 将关键元素(要搜索的元素称为关键元素)与已排序数组的中间元素进行比较。

• 步骤4 − 如果关键元素小于或等于已排序数组的中间元素，则忽略第二半部分元素，因为关键元素小于中间元素。 因此，必定存在于第一个元素和中间元素之间。

• 步骤6 − 如果关键元素大于中间元素，则忽略已排序数组的第一半，并考虑中间元素到最后一个元素之间的元素。

• 步骤7 − 在这些元素中，再次将关键元素与被拆分数组的中间元素进行比较，并重复相同的过程。 如果关键元素大于被拆分数组的中间元素，则忽略第一半。

• 步骤8 − 如果关键元素小于或等于被拆分数组的中间元素，则忽略被拆分数组的中间元素的第二半。 这样就可以按照数组的任一半搜索元素。

因此，与线性搜索相比，复杂度减少了一半或更多，因为在第一步中将删除或不考虑一半的元素。 二分查找的最佳情况时间复杂度为“ O（1）”。 二进制搜索的最坏情况时间复杂度为“O（logn）”。 这就是二进制搜索算法的工作方式。 让我们考虑一个例子，并应用二分搜索算法来查找数组中的关键元素。

实例

在此示例中，我们将学习使用递归方法的二分搜索算法在数组中查找元素的过程。

def recursive_binary(arr, first, last, key_element):
   if first <= last:
      mid = (first + last) // 2 
   if arr[mid] == key_element:
      return mid
   elif arr[mid] > key_element:
      return recursive_binary(arr, first, mid - 1, key_element)
   elif arr[mid] < key_element:  
      return recursive_binary(arr, mid + 1, last, key_element)  
   else:  
      return -1 

arr = [20, 40, 60, 80, 100] 
key = 80 
max_size = len(arr)
result = recursive_binary(arr, 0, max_size - 1, key)  
if result != -1:  
   print("该元素", key, "在位置为", (result + 1), "的下标为", (result)) 
else:  
   print("该元素不在该数组中") 

输出

上述程序的输出如下−

该元素 80 在位置为 4 的下标为 3

例子

在这个例子中，我们将学习使用迭代二分查找在数组中查找元素的过程。

def iterative_binary(arr, last, key_element):
   first = 0
   mid = 0
   while first <= last: 

      mid = (first + last) // 2 
      if arr[mid] < key_element:
         first = mid + 1 

      elif arr[mid] > key_element: 
         last = mid - 1 

      else: 
         return mid 

   return -1 

arr = [20, 40, 60, 80, 100] 
key = 80 
max_size = len(arr)

result = iterative_binary(arr, max_size - 1, key)  

if result != -1:  
   print("该元素", key, "在位置为", (result + 1), "的下标为", (result)) 
else:  
   print("该元素不在该数组中")

输出

上述程序的输出如下−

该元素 80 在位置为 4 的下标为 3

这就是二分搜索算法的工作原理。我们可以肯定地说，基于时间复杂度的概念，二分搜索算法比线性搜索算法更高效。通过使用这种类型的算法可以搜索数组的元素。虽然解决问题的过程不同，但结果不会波动。这是使用多种算法检查输出一致性的一个优势。