When developing algorithms for solving many problems, the problem often arises of implementing the search for a certain group of data according to specified criteria. When exploring an ordered or unordered sequence, searches can be performed using different methods. In the general case, to solve the search problem, a certain data array is considered, in which it is required to find a given element.
Instructions
Step 1
The easiest way to find a known element in a data array is to iterate over its values. This algorithm is optimal for small amounts of information. Its essence lies in traversing a known data sequence (array) and comparing each element with the desired value. If a match is found, depending on the specified criteria, the search can be completed or continued to the end of the array.
Step 2
However, despite the simplicity of the implementation of this method, its use is undesirable in arrays containing large amounts of information, since this significantly increases the resource intensity of the algorithm. To optimize the search in this case, it is better to pre-sort the values in the array and implement the search algorithms: by a binary tree, by the Fibonacci tree, by the extrapolation method.
Step 3
When working with an ordered array, use a more efficient algorithm - the binary search method. Its essence lies in the fact that in the process of enumerating the boundaries of the interval approach each other, thus narrowing the search area. Compare the value you are looking for with the numbered element of the array. If the sample matches the element, the problem is considered solved. If the desired item is greater than the middle element, then further search must be carried out in the part of the array located to the right of the middle element (from the beginning of the array to the middle element-1). If the search is less than the middle element, then the search continues in the part of the array from the middle to the last element. Having determined a new area for search, the described algorithm is repeated, identifying matches or narrowing the area of processing. This scheme is correct for a descending array.
Step 4
Particular problems of finding the minimum or maximum element in a given sequence are solved by assigning the initial element as the desired one. Next, a sequential enumeration of the remaining array values is carried out: the second with the first, the third with the first, etc. When comparing the value taken as a reference, it becomes clear whether there is an element in the array that is more consistent with the given condition (minimum or maximum). When one is found, it is already taken as a standard, and the enumeration continues from the current position to the end of the array. As a result, the minimum (or maximum) value in this group is the element that was last recognized as the standard.
