Lecture
Search with a sentinel – is a modification of the sequential search algorithm that speeds up the process by defining a boundary element.
There exists a modification of the sequential search algorithm that speeds up the search. This modification is a small improvement on the search algorithm discussed earlier.
The idea of search with a sentinel is to avoid checking the boundary condition of the set on every iteration of the loop. This can be achieved by placing a so-called sentinel in the given set. A sentinel is understood to be any element that satisfies the search condition. This limits the change in the index.
Exiting the loop, in which now only the search condition remains, can happen either at the found element or at the sentinel. There are two ways to place a sentinel: with an additional element, or in place of the array's outermost element.
The linear search algorithm can be simplified by getting rid of the check of the extra condition, if one is certain that the array is guaranteed to contain an element matching the pattern. Sometimes the truth of this condition follows from knowing how the array and the search pattern were constructed. But one can also force this condition to hold by building a "sentinel" into the array that prevents the search from going beyond the array's bounds. For this purpose, the array is extended by one element, and the "sentinel" – the search pattern – is written as the last element. In this case the search will always find the pattern. If the pattern is not among the array's "native" elements, it will be encountered at the end as the "sentinel."
For simplicity, the second version of the linear search algorithm is more suitable. Here is an implementation of this scheme:
Note that the method itself does not build any sentinels. It merely states a precondition requiring the existence of a sentinel element in the array. Responsibility for satisfying the precondition lies with the client. Whoever calls the method must ensure the precondition is met. Such are the principles of design by contract. Of course, one can build another implementation in which the method itself takes on responsibility for building the sentinel.
Note also that search with a sentinel runs faster, but the time complexity of the algorithm remains the same, O(n), where n – is the number of elements in the set. Of much greater interest are methods that not only run fast, but also implement algorithms with lower complexity.
Comments