Data Structures Algorithms 简明教程
Data Structures - Searching Algorithms
在前一节中，我们讨论了各种排序技术以及可以使用它们的情况。然而，执行排序的主要思想是以有序的方式排列数据，使在排序数据中搜索任何元素变得更加容易。
In the previous section, we have discussed various Sorting Techniques and cases in which they can be used. However, the main idea behind performing sorting is to arrange the data in an orderly way, making it easier to search for any element within the sorted data.
Searching 是在大量数据中找到特定记录（可以是单个元素或小块）的过程。数据可以存在于各种形式：数组、链表、树、堆和图形等。随着如今数据的增加，有多种技术可以执行搜索操作。
Searching is a process of finding a particular record, which can be a single element or a small chunk, within a huge amount of data. The data can be in various forms: arrays, linked lists, trees, heaps, and graphs etc. With the increasing amount of data nowadays, there are multiple techniques to perform the searching operation.
Searching Algorithms in Data Structures
可以对数据结构应用各种搜索技术来检索特定数据。只有在搜索操作返回所需元素或数据时，才认为它成功；否则，搜索方法不成功。
Various searching techniques can be applied on the data structures to retrieve certain data. A search operation is said to be successful only if it returns the desired element or data; otherwise, the searching method is unsuccessful.
有两种搜索技术可以归入其中。它们是 -
There are two categories these searching techniques fall into. They are −
-
Sequential Searching
-
Interval Searching
Sequential Searching
顾名思义，顺序搜索操作顺序遍历数据的每个元素以查找所需数据。对于这种类型的搜索，数据不必以有序方式排列。
As the name suggests, the sequential searching operation traverses through each element of the data sequentially to look for the desired data. The data need not be in a sorted manner for this type of search.
Example - 线性搜索
Example − Linear Search
Fig. 1: Linear Search Operation
Fig. 1: Linear Search Operation
Interval Searching
与顺序搜索不同，区间搜索操作要求数据以排序方式排列。此方法通常按区间搜索数据；它可以通过将数据分为多个子部分或跳过索引来查找元素来完成。
Unlike sequential searching, the interval searching operation requires the data to be in a sorted manner. This method usually searches the data in intervals; it could be done by either dividing the data into multiple sub-parts or jumping through the indices to search for an element.
Example - 二分搜索、跳跃搜索等
Example − Binary Search, Jump Search etc.
Fig. 2: Binary Search Operation
Fig. 2: Binary Search Operation
Evaluating Searching Algorithms
通常，并非所有搜索技术都适用于所有类型的数据结构。在某些情况下，顺序搜索更可取，而在其他情况下，区间搜索更可取。通过检查每种搜索方法在特定输入上所用的运行时间来完成这些搜索技术的评估。
Usually, not all searching techniques are suitable for all types of data structures. In some cases, a sequential search is preferable while in other cases interval searching is preferable. Evaluation of these searching techniques is done by checking the running time taken by each searching method on a particular input.
这就是渐近符号派上用场的地方。如需详细了解渐近符号，请访问 click here.
This is where asymptotic notations come into the picture. To learn more about Asymptotic Notations, please click here.
简单来说，程序可以有三种不同的时间复杂度情况。它们是：
To explain briefly, there are three different cases of time complexity in which a program can run. They are −
-
Best Case
-
Average Case
-
Worst Case
我们主要只关注最佳情况和最差情况的时间复杂度，因为平均情况难以计算。而且由于运行时间是以提供给程序的输入量为基础的，因此最差情况的时间复杂度最能描述任何算法的性能。
We mostly concentrate on the only best-case and worst-case time complexities, as the average case is difficult to compute. And since the running time is based on the amount of input given to the program, the worst-case time complexity best describes the performance of any algorithm.
例如，线性搜索的最佳情况时间复杂度为 O(1) ，其中在第一次迭代中找到了所需元素；而当程序遍历所有元素仍未找到元素时，最差情况时间复杂度为 O(n) 。这被标记为不成功的搜索。因此，线性搜索的实际时间复杂度被视为 O(n) ，其中 n 是输入数据结构中存在的元素的数量。
For instance, the best case time complexity of a linear search is O(1) where the desired element is found in the first iteration; whereas the worst case time complexity is O(n) when the program traverses through all the elements and still does not find an element. This is labelled as an unsuccessful search. Therefore, the actual time complexity of a linear search is seen as O(n), where n is the number of elements present in the input data structure.
许多类型的搜索方法用于在各种数据结构中搜索数据条目。其中一些包括：
Many types of searching methods are used to search for data entries in various data structures. Some of them include −
-
Ubiquitous Binary Search
我们将在以下章节中详细探讨每种搜索方法。
We will look at each of these searching methods elaborately in the following chapters.