Data Structures Algorithms 简明教程

Linear Search Algorithm

线性搜索是一种顺序搜索算法。在此方法中，遍历输入数组中的每个元素，并将其与要查找的关键元素进行比较。如果在数组中找到匹配项，则搜索成功；如果没有找到匹配项，则搜索失败，并给出最坏情况的时间复杂度。

Linear search is a type of sequential searching algorithm. In this method, every element within the input array is traversed and compared with the key element to be found. If a match is found in the array the search is said to be successful; if there is no match found the search is said to be unsuccessful and gives the worst-case time complexity.

例如，在给定的动画图表中，我们正在搜索元素 33。因此，线性搜索方法从第一个元素开始顺序搜索它，直到找到匹配项。这会返回一个成功的搜索。

For instance, in the given animated diagram, we are searching for an element 33. Therefore, the linear search method searches for it sequentially from the very first element until it finds a match. This returns a successful search.

在同一图表中，如果我们必须搜索元素 46，则它会返回一个不成功的搜索，因为输入中没有 46。

In the same diagram, if we have to search for an element 46, then it returns an unsuccessful search since 46 is not present in the input.

Linear Search Algorithm

线性搜索的算法相对简单。过程从要搜索的输入数组的第一个索引开始。

The algorithm for linear search is relatively simple. The procedure starts at the very first index of the input array to be searched.

Step 1 − 从输入数组的第 0 个索引开始，将键值与第 0 个索引中存在的那个值进行比较。

Step 1 − Start from the 0th index of the input array, compare the key value with the value present in the 0th index.

Step 2 − 如果值与键匹配，则返回找到值的位置。

Step 2 − If the value matches with the key, return the position at which the value was found.

Step 3 − 如果值与键不匹配，则比较数组中的下一个元素。

Step 3 − If the value does not match with the key, compare the next element in the array.

Step 4 − 重复步骤 3，直到找到匹配。返回找到匹配的位置。

Step 4 − Repeat Step 3 until there is a match found. Return the position at which the match was found.

Step 5 − 如果搜索不成功，则打印元素不存在于数组中并退出程序。

Step 5 − If it is an unsuccessful search, print that the element is not present in the array and exit the program.

Pseudocode

procedure linear_search (list, value)
   for each item in the list
      if match item == value
         return the item's location
      end if
   end for
end procedure

Analysis

线性搜索顺序遍历每个元素，因此，当在第一次迭代中找到该元素时为最佳情况。最佳情况时间的复杂度是 O(1) 。

Linear search traverses through every element sequentially therefore, the best case is when the element is found in the very first iteration. The best-case time complexity would be O(1).

但是，线性搜索方法的最坏情况是未成功的搜索，即未在数组中找到键值，它执行 n 次迭代。因此，线性搜索算法的最坏情况时间复杂度是 O(n) 。

However, the worst case of the linear search method would be an unsuccessful search that does not find the key value in the array, it performs n iterations. Therefore, the worst-case time complexity of the linear search algorithm would be O(n).

Example

让我们看看使用线性搜索方法在数组中逐步搜索键元素（假设为 47）。

Let us look at the step-by-step searching of the key element (say 47) in an array using the linear search method.

Step 1

线性搜索从第 0 个索引开始。将键元素与第 0 个索引中的值 34 进行比较。

The linear search starts from the 0th index. Compare the key element with the value in the 0th index, 34.

但是，47 ≠ 34。因此，它移至下一个元素。

However, 47 ≠ 34. So it moves to the next element.

Step 2

现在，将该键与数组的第一个索引中的值进行比较。

Now, the key is compared with value in the 1st index of the array.

仍然是 47 ≠ 10，使得算法移至另一个迭代。

Still, 47 ≠ 10, making the algorithm move for another iteration.

Step 3

将下一个元素 66 与 47 进行比较。两者都不匹配，因此算法比较了后面的元素。

The next element 66 is compared with 47. They are both not a match so the algorithm compares the further elements.

Step 4

现在，第 3 个索引中的元素 27 与键值 47 进行比较。它们不相等，因此算法推进到检查下一个元素。

Now the element in 3rd index, 27, is compared with the key value, 47. They are not equal so the algorithm is pushed forward to check the next element.

Step 5

比较数组中第 4 个索引处的元素 47 与键 47。可以看出两个元素匹配。现在，返回 47 存在的位置，即 4。

Comparing the element in the 4th index of the array, 47, to the key 47. It is figured that both the elements match. Now, the position in which 47 is present, i.e., 4 is returned.

获得的输出是“在第 4 个索引处找到元素”。

The output achieved is “Element found at 4th index”.

Implementation

在本教程中，可以在四种编程语言中看到线性搜索程序的实现。该函数将输入元素与键值进行比较，并返回该键在数组中的位置，或者如果数组中不存在该键，则返回搜索不成功的提示。

In this tutorial, the Linear Search program can be seen implemented in four programming languages. The function compares the elements of input with the key value and returns the position of the key in the array or an unsuccessful search prompt if the key is not present in the array.