Python程序在数组中搜索元素

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

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

线性搜索

线性搜索技术也称为顺序搜索。 “顺序搜索”这个名称的含义绝对是由该搜索算法遵循的过程来证明的。它是一种方法或技术，用于在 Python 中查找数组或列表中的元素。

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

算法

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

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

• 步骤 3 - 如果该元素不存在于数组中，则用户将被告知未找到该元素。这样，算法就处理好了

总的来说，线性搜索算法对于小于或等于100的小型数组或小型列表来说，比较适合和高效，因为它会检查并比较每个元素。

• 如果所需元素位于备份的最后位置，将会消耗更多时间。

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

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

• 线性搜索算法在最坏情况下的时间复杂度是“ O( n ) ”。在这种情况下，该元素将出现在数组的最后一个位置，即索引为“ n-1 ”。

示例

在下面的示例中，我们将学习使用线性搜索在阵列中查找元素的过程。

雷雷

输出

上述程序的输出如下：

雷雷

示例（递归）

在下面的例子中，我们将学习使用梯度方法在阵列中进行线性搜索的过程。

雷雷

输出

上述程序的输出如下：

雷雷

二分查找

二分查找算法与线性查找算法相当不同。它完全遵循不同的过程来搜索集群中的元素。它通常只考虑集群集群。

如果阵列在某些情况下没有排序，则对阵列进行排序，然后开始二分搜索算法的过程。一旦阵列被二分搜索算法，则考虑首先被排序，然后算法被分配磁盘。

算法

• 步骤 1 − 对仓库进行排序是第一步。

• Step 2 - 数组排序后，数组被视为两半。一半是从排序数组的第一个元素到中间元素，后半部分是从排序数组的中间元素之后的元素到最后一个元素。

• 步骤 3 - 将关键元素（应该搜索的元素称为关键元素）与排序数组的中间元素进行比较。

• 步骤 4 - 如果键元素小于或等于排序数组的中间元素，则后半部分元素将被进一步忽略，因为键元素小于中间元素。所以，当然，该元素必须存在于第一个元素和中间元素之间。

• 步骤 6 - 如果键元素大于中间元素，则忽略排序数组的前半部分，并考虑从中间元素到最后一个元素的元素。

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

• 第8步 - 如果关键元素小于或等于被分割数组的中间元素，则被分割数组的后半部分将被忽略。通过这种方式，元素将在数组的任意一半中进行搜索。

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

Example

In this example, we are going to learn about the process of searching an element in an array using Binary search in recursive approach.

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("The element", key, "is present at index", (result), "in the position", (result + 1)) 
else:  
   print("The element is not present in the array") 

Output

上述程序的输出如下：

The element 80  is found at the index 3 and in the position 4

Example

In this example, we are going to learn about the process of searching an element in an array using Binary search in iterative approach.

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("The element", key, "is present at index", (result), "in the position", (result + 1)) 
else:  
   print("The element is not present in the array")

Output

上述程序的输出如下：

The element 80  is found at the index 3 and in the position 4

这是二分搜索算法的工作原理。根据时间复杂度的概念，我们可以肯定二分搜索算法比线性搜索算法更高效，时间复杂度在其中起着重要的作用。通过使用这种类型的算法，可以搜索数组中的元素。尽管用于解决问题的过程不同，但结果不会波动。这是使用多种算法检查输出一致性的一个优点。

以上是Python程序在数组中搜索元素的详细内容。更多信息请关注PHP中文网其他相关文章！