数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究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 ("The element", key," is found at the index " ,(result), "and in the ", (result+1), "position")
else:
print ("The element %d is not present in the given array" %(key))
输出
上述程序的输出如下所示：
The element 8 is found at the index 8 and in the 9 position
示例（递归）
在下面的示例中，我们将学习使用递归方法的线性搜索在数组中搜索元素的过程。
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 ("The element", key," is found at the index " ,(result), "and in the ", (result+1), "position")
else:
print ("The element %d is not present in the given array" %(key))
输出
上述程序的输出如下所示：
The element 8 is found at the index 8 and in the 9 position
二分搜索
二分搜索算法与线性搜索算法完全不同。它遵循完全不同的程序来从数组中搜索元素。它通常只考虑排序后的数组。
如果数组在某些情况下未排序，则会对数组进行排序，然后开始二分搜索算法的过程。一旦二分搜索算法考虑了数组，它就会先对其进行排序，然后将算法应用于数组。
算法
步骤 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("The element", key, "is present at index", (result), "in the position", (result + 1))
else:
print("The element is not present in the array")
输出
上述程序的输出如下所示：
The element 80 is found at the index 3 and in the position 4
示例
在这个例子中，我们将学习使用迭代方法的二分搜索在数组中搜索元素的过程。
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")
输出
上述程序的输出如下所示：
The element 80 is found at the index 3 and in the position 4
这就是二分搜索算法的工作原理。根据起主要作用的时间复杂度概念，我们肯定可以说二分搜索算法比线性搜索算法更有效。通过这种方式，可以使用这种类型的算法搜索数组的元素。虽然解决问题的过程不同，但结果不会波动。这是使用多种算法来检查输出一致性的一种优势。
6000+ 次浏览
