Quite often, programmers, even beginners, are faced with the fact that there is a set of numbers in which you need to find a certain number. This collection is called an array. And to find the desired element in it, there are a huge variety of ways. But the simplest among them can rightfully be considered a binary search. What is the given method? And how to implement binary search? Pascal is the easiest environment for organizing such a program, so we will use it for study.
First, we’ll analyze the advantages of this method, because we can understand
what is the point in studying this topic. So, suppose there is an array with a dimension of at least 100,000,000 elements in which you need to find a specific one. Of course, this problem can easily be solved by a simple linear search, in which we will use the loop to compare the desired element with all those in the array. The problem is that implementing this idea will take too much time. In a simple Pascal program for several procedures and with three lines of the main text, you will not notice this, but when you start more or less large projects with a large number of branches and good functionality, the finished program will take too long to load. Especially if the computer has poor performance. Therefore, there is a binary search, which reduces the search time by at least half.
So, what is the principle of operation of this method? It’s worth saying right away that binary search does not work in any array, but only in a sorted set of numbers. At each next step, the middle element of the array is taken (meaning by the number of the element). If the desired number is greater than the average, then everything that is on the left, that is, less than the middle element, can be discarded and not searched there. Conversely, if less than average - among those numbers on the right, you can not search. Next, we select a new search area where the first element will be the middle element of the entire array, and the last will remain the last. The average number of the new region will be ¼ of the entire segment, that is (the last element + the middle element of the entire array) / 2. Again the same operation is performed - comparison with the average number of the array. If the desired value is less than the average, we discard the right-hand side, and do the same further, until this middle element is found.
Of course, it is best to look at an example of how binary search is written. Pascal is suitable for anyone here - the version is not important. Let's write a simple program.
It will have an array from 1 to h called "massiv", a variable denoting the lower bound of the search, called "niz", the upper bound, called "verh", the middle element of the search is "sredn"; and the number you are looking for isk.
So, first we assign the upper and lower boundaries of the search interval:
niz: = 1; verh: = h + 1;
Then we organize the cycle "while the lower is less than the upper boundary":
While niz <verh - 1 do begin
At each step, divide the segment by 2:
sredn: = (niz + verh) div 2; {we use div function because we divide without remainder}
Every time we check. If the average is equal to the desired one, we interrupt the cycle, since the desired element has already been found:
if sredn = isk then break;
If the middle element of the array is larger than the desired one, we discard the right side, that is, we assign the middle element to the upper boundary:
if massiv [sredn]> isk then verh: = sredn;
And if on the contrary, then we make it the lower boundary:
else niz: = sredn; end;
That is all that will be in the program.
Let's see how the binary method will look in practice. Let's take such an array: 1, 3, 5, 7, 10, 12, 18 and we will look for the number 12 in it.
In total, we have 7 elements, so the fourth will be the average, its value is 7.
Since 12 is greater than 7, we can discard elements 1,3 and 5. Then we have 4 numbers left, 4/2 without a remainder is 2. So, the new middle element will be 10.
Since 12 is greater than 10, we discard 7. Only 10, 12 and 18 remain.
Here the middle element is already 12, this is the desired number. Task completed - number 12 found.