CATEGORIES:
BiologyChemistryConstructionCultureEcologyEconomyElectronicsFinanceGeographyHistoryInformaticsLawMathematicsMechanicsMedicineOtherPedagogyPhilosophyPhysicsPolicyPsychologySociologySportTourism
The binary chop search algorithm
You have seen how we can reduce the not in array time fairly drastically, by sorting an array. By using the binary chop algorithm, to search a sorted array we can cut that time even further. The whole concept of this algorithm is to eliminate half of an array from the search at each step, until the required element is either found or not found. The consequence of this is that both the not in array time, and the found in array time will be roughly the same, and will be reduced to a tiny amount compared with a straightforward linear search on either a sorted or an unsorted array. To use the binary chop algorithm, the array must be sorted unlike with the linear search algorithm, where sorting has no effect on either of the times. In this algorithm, assume found to be declared as a boolean, and mid_point, top_end, and bottom_end to be type INTEGER. Also MAX is a CONST equal to ten, and searched_for_value to be of the same type as the array elements.
found := FALSE; top_end := number_of_loaded_elements; mid_point := 0; { arbitrarily initialise to zero } bottom_end := 1; WHILE (NOT found) AND (bottom_end <= top_end) DO BEGIN mid_point := (top_end + bottom_end) DIV 2; { integer division } IF {1} test_array[mid_point] = searched_for_value then found := TRUE { no further action required } ELSE IF {2} test_array[mid_point] < searched_for_value THEN bottom_end := (mid_point + 1) { value in upper half } ELSE {3} top_end := (mid_point - 1); { value in lower half } END;
Here is the initial condition before the binary chop algorithm starts. Also suppose we are searching for the value 9.
Figure 8 - Binary-chop : Initial condition
Now we enter the WHILE loop, and perform the first calculation.
This will yield
therefore
The integer division operator discards anything after the decimal point. Even if that part is .9999 it will not round up.
therefore
The condition after the first loop is shown below.
Figure 9 - Binary-chop : After first loop
In the next loop,
therefore
and then ELSE condition in Line 3 becomes true and so,
therefore
The condition after the second loop is shown below.
Figure 10 - Binary-chop : After second loop
In the next loop,
therefore
and then the ELSE - IF condition in line 2 becomes true and so
therefore
Figure 11 - Binary-chop : After third loop
In the next loop,
therefore
Now line 1 becomes true, and so the BOOLEAN found becomes TRUE, and the variable mid_point yields the position of the searched for value.
Figure 12 - Binary-chop : After fourth loop
I promised you that this would operate a search, quite a bit faster than a simple linear search, and so the next program will demonstrate this. Since this is just a demonstration program I have used a FOR loop to load the array the benefit of this is that it is already in order. So the search can run without waiting for the array to being sorted.
Program 5
PROGRAM binary_chop(INPUT,OUTPUT); { a demonstration program, which searches through an integer array using the binary chop algorithm } CONST MAX = 200000; TYPE INTEGER_ARRAY = ARRAY[1..MAX] OF INTEGER; VAR found : BOOLEAN; I, { for loop counter } top_end, mid_point, bottom_end : INTEGER; { array counters } test_array : INTEGER_ARRAY; searched_for_value : INTEGER; BEGIN { load up array with in-order integers } FOR I := 1 TO MAX DO test_array[I] := I; WRITE('Enter value you wish to search for : '); READLN(searched_for_value); found := FALSE; top_end := MAX; bottom_end := 1; WHILE (NOT found) AND (bottom_end <= top_end) DO BEGIN mid_point := (top_end + bottom_end) DIV 2; { integer division } IF test_array[mid_point] = searched_for_value THEN found := TRUE { no further action required } ELSE IF test_array[mid_point] < searched_for_value THEN bottom_end := (mid_point + 1) { value in upper half } ELSE top_end := (mid_point - 1); { value in lower half } END; IF found THEN BEGIN WRITE('The value searched for is in'); WRITELN(' element ',mid_point:0); END ELSE WRITELN('Value Not Found'); END. { program binary_chop }
When you run this program, you will find that the not in array time and the found in array time is the same.
Date: 2016-03-03; view: 877
| <== previous page | | | next page ==> |
| Selection sort, algorithm | | | Multi-Dimensional Arrays |