极客笔记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
这就是二分查找算法的工作原理。根据时间复杂度的概念来说，可以肯定地说二分查找算法比线性查找算法更有效。通过使用这种类型的算法，可以搜索数组中的元素。尽管用于解决问题的过程不同，结果不会波动。这是使用多种算法来检查输出的一种优势。