Binary search is one of the easiest ways to find an element in an array

Quite often, programmers, even beginners,face that there is a set of numbers in which it is necessary to find a certain number. This collection is called an array. And to find the right element in it, there are a lot of ways. But the simplest among them by right can be considered a binary search. What is the method? And how to implement a binary search? Pascal is the simplest medium for organizing such a program, so we will use it for study.

First, we will analyze what the advantages of this method are, after all, so we can understand,

what is the point in studying this topic. So, suppose there's an array with a dimension of at least 100000000 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 cycle to compare the desired element with all those that exist in the array. The problem is that the implementation of this idea will take too long. In a simple Pascal program for several procedures and with three lines of the main text, you will not notice it, but when you start more or less large projects with a lot of branching and good functionality, the finished program will be loaded for too long. Especially in the event that the computer has poor performance. Therefore, there is a binary search, which reduces the search time by at least twice.

So, what is the working principle of thismethod? It's worth mentioning 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 (referring to the element number) is taken. If the desired number is greater than the average, then everything that is on the left, that is, less than the average element, can be discarded and not searched there. Conversely, if less than average, among the numbers on the right, you can not look for them. Next, we'll select a new search area, where the middle element of the whole array will be the first element, and the last one will remain the last one. The average number of the new area will be ¼ of the entire segment, that is (the last element + the average 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, discard the right-hand side, and do the same until until this middle element is found.

Of course, it's best to look at an example of how a binary search is written. Pascal here is suitable for anyone - the version is not important. Let's write a simple program.

It will have an array from 1 to h named"massiv", a variable denoting a lower search boundary, called "niz", an upper bound named "verh", the middle element of the search is "sredn"; and the required number is "isk".

So, first assign the upper and lower boundaries of the search interval:

niz: = 1;
verh: = h + 1;

Then we organize the cycle "while the bottom is less than the upper limit":

While niz <verh - 1 do
begin

At each step, divide the segment by 2:

sredn: = (niz + verh) div 2; {use the div function because we divide the remainder}

Every time we conduct a check. If the average is equal to the desired one, we interrupt the cycle, since the desired element is already found:

іf sredn = isk then break;

If the average element of the array is greater than the one we are looking for, discard the left 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's all that will be in the program.

We will analyze how the binary method will look in practice. We take such an array: 1, 3, 5, 7, 10, 12, 18 and look for the number 12 in it.

In total, we have 7 elements, so the average will be the fourth, its value 7.

Since 12 is greater than 7, the elements 1,3 and 5 can be discarded. Next, we have 4 numbers left, 4/2 without remainder is 2. So, the new middle element will be 10.

Since 12 is more than 10, discard 7. Only 10, 12 and 18 are left.

Here the middle element is already 12, this is the required number. The task is completed - the number 12 is found.