Python程序在数组中搜索元素
In Python, there are mainly two searching algorithms that are majorly used. Out of those, the first one is Linear Search and the second one is Binary Search.
These two techniques are majorly used in order to search an element from the given array or from the given list also. While searching an element, there are two methodologies that can be followed in any kind of algorithm. One of those is recursive approach and the other is iterative approach. Let us discuss both algorithms in both approaches and solve similar problems.
Linear Search
The Linear Search technique is also known as Sequential search. The meaning of the name “ Sequential search ” is definitely justified by the process followed by this search algorithm. It is a method or technique which is used in order to find the elements within an array or a list in Python.
它被认为是所有其他搜索算法中最简单和最容易的。但是，这个算法的唯一缺点是效率不高。这就是为什么不经常使用线性搜索的主要原因。
算法
Step 1 − It searches for an element in a sequential order just by comparing the desired element with each element present in the given array.
步骤 2 − 如果找到所需的元素，则会将元素的索引或位置显示给用户。
Step 3 − If the element is not present within the array, then the user will be informed that the element is not found. In this way, the algorithm is processed.
In general, Linear search algorithm is comparatively suitable and efficient for small arrays or small lists which has a size less than or equal to 100 as it checks and compares with each element.
如果所需元素位于数组的最后位置，将会消耗更多时间。
线性搜索算法在最佳情况下的时间复杂度为“ O( 1 ) ”。在这种情况下，元素将位于数组的第一个位置，即索引为“ 0 ”。
The Time complexity of Linear Search algorithm in average case is “ O( n ) ”. In this case, the element will be present in the middle position of the array, i.e., with the index “ ( n – 1 ) / 2 ” or “ (( n – 1 ) / 2 )+ 1 ”.
The Time complexity of Linear Search algorithm in worst case is “ O( n ) ”. In this case, the element will be present in the last position of the array, i.e., with the index “ n-1 ”.
Example
在下面的示例中，我们将学习使用线性搜索在数组中查找元素的过程。
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)) 登录后复制
