Lecture
It is clear that there are no other ways to speed up the search, unless, of course, there is still any information about the data, among which there is a search. It is well known that a search can be made significantly more efficient if the data is streamlined. Imagine a telephone directory in which the names will not be arranged in order. This is something completely useless! Therefore, we present an algorithm based on the knowledge that array a is ordered, i.e. satisfies the condition
A k : 1 k k-1 a k
The basic idea is to randomly select some element, suppose am, and compare it with the search argument x. If it is equal to x, then the search ends, if it is less than x, then we conclude that all elements with indices less than or equal to m can be excluded from further search; if it is greater than x, then indices greater than and equal to m are excluded. This consideration leads us to the following algorithm (it is called “search by division in half”). Here, the two index variables L and R mark the left and right ends of the array section a, respectively, where the required element can still be found.
L: = 0;
R: = N-1;
found: = FALSE;
WHILE (L Ј R) AND NOT found DO
m: = any value between L and R;
IF a [m] = x THEN found: = TRUE;
IF a [m]
ELSE R: = m-1;
END;
END;
The cycle invariant, i.e. The condition that runs before each step is:
(L R) AND (A k : 0 k k k : R k > x)
what the result is derived from
found OR ((L> R) AND (A k : 0 k k k : R k > x))
where it comes from
(a m = x) OR (A k : 0 k
The choice of m is completely arbitrary in the sense that the correctness of the algorithm does not depend on it. However, the choice affects its effectiveness. It is clear that our task is to exclude at every step from further search, whatever the result of the comparison, as many elements as possible. The best solution would be to select the middle element, since in this case half of the array will be excluded. As a result, the maximum number of comparisons is log N, rounded to the nearest integer. Thus, the above algorithm significantly benefits compared with a linear search, because there the expected number of comparisons is N / 2.
Efficiency can be somewhat improved by reversing the headings of conditional statements. The equality test can be performed secondarily, since it occurs only once and leads to the end of the work. But more importantly, the following consideration: is it possible, like in a linear search, to find such a solution, which would again simplify the termination condition. And we really find such a fast algorithm as soon as we abandon the naive desire to end the search while fixing a match. At first glance, this seems strange, but upon careful examination it turns out that the efficiency gain at each step exceeds the loss from comparison with several additional elements. Recall that the number of steps in the worst case is log N. The fast algorithm is based on the following invariant:
(A k : 0 k k k : R k k x)
the search continues until both sections "cover" the entire array.
L: = 0;
R: = N;
WHILE L
m: = (L + R) DIV 2;
IF a [k]
ELSE R: = m;
END
END
The termination condition is L i R, but is it attainable? To prove this, we need to show that in all circumstances the difference RL decreases at every step. At the beginning of each step L
Options:
1. Find the smallest element in array A using a linear search.
2. Search for elements in array A that are greater than 30.
3. Display on screen all the numbers in array A multiples of 3 (3,6,9, ...) using a linear search.
4. Find all items whose module is greater than 20 and less than 50, using linear search.
5. To display on the screen all the numbers in array A are multiples of 4 (4.8, ...) using a linear search.
6. To display a message, which numbers are more relative to 50, using a linear search.
7. Find the element in array A and find the number of comparisons using linear search.
8. Search for items randomly using a binary search.
9. It is given a list of car numbers (345, 368, 876, 945, 564, 387, 230), to find where the car with the specified number is located, binary search.
10. Search every second element in the list and the number of comparisons.
11. Find an element with a given key using a binary search.
Comments
To leave a comment
Structures and data processing algorithms.
Terms: Structures and data processing algorithms.