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.

mid_point := (top_end + bottom_end) DIV 2;

This will yield

mid_point := (10+1) DIV 2;

therefore

mid_point := 5;

The integer division operator discards anything after the decimal point. Even if that part is .9999 it will not round up.

bottom_end := (mid_point + 1);

therefore

bottom_end := 6;

The condition after the first loop is shown below.

Figure 9 - Binary-chop : After first loop

In the next loop,

mid_point := (6 + 10) DIV 2;

therefore

mid_point := 8;

and then ELSE condition in Line 3 becomes true and so,

top_end := (8 - 1);

therefore

top_end := 7;

The condition after the second loop is shown below.

Figure 10 - Binary-chop : After second loop

In the next loop,

mid_point := (7 + 6) DIV 2;

therefore

mid_point := 6;

and then the ELSE - IF condition in line 2 becomes true and so

bottom_end := (6 + 1);

therefore

bottom_end := 7;

Figure 11 - Binary-chop : After third loop

In the next loop,

mid_point := (7 + 7) DIV 2;

therefore

mid_point := 7;

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: 748

<== previous page	\|	next page ==>
Selection sort, algorithm	\|	Multi-Dimensional Arrays

doclecture.net - lectures - 2014-2024 year. Copyright infringement or personal data (0.007 sec.)