Last Updated:

Binary search algorithm

When the search for an element must be carried out in a sequence ordered in ascending or descending order, then the binary (binary) search algorithm is applied. The method uses the "divide and conquer" strategy, namely: the given sequence is divided into two equal parts and the search is carried out in one of these parts, which is then also divided in two, and so on until the presence of the desired element or its absence is detected.

To use this operation, reducing the search area by half each time, is allowed only on the basis of the fact that the elements of the sequence are pre-ordered. Having found the average element (it is not difficult to do this, knowing the number of elements of the array), and comparing its value with the desired one, you can confidently say where the desired element is relative to the average element.

 

Further, we will assume that the elements of the array are arranged in ascending order, since there is no significant difference in how exactly they are ordered: in ascending or descending order. We will also mark the boundaries of the search area through left and right - the far left and far right elements, respectively.

The course of the algorithm, divided into stages, is as follows:

  1. the search zone (in the first step it is the entire array) is divided into two equal parts, by determining its middle (mid) element;
  2. the middle element is compared with the key element, the result of this comparison will be one of three cases:
      • key<mid. The far-right border of the search scope is the element facing the middle (right ← mid-1);
      • key>mid. The leftmost boundary of the search scope is left ← mid+1;
      • key=mid. The values of the average and the desired elements coincide, therefore, the element is found, the algorithm is completed.
  3. if there are no elements left for verification, the algorithm is terminated, otherwise step 1 is moved.

The following table shows a specific integer array, and a step-by-step execution of the binary search algorithm on its elements. To save space in the table, left, right, and mid have been replaced by a, b, and c.

Search Binary Algorithm

There is a sequence of integers arranged in ascending order, as well as a key - the number 16. Initially, the boundary elements are elements numbered 1 and 9, and values 1 and 81. The number of the middle element is calculated, for which, as a rule, the formula (right + left) / 2, or left + (right-left) / 2 is used (hereinafter, the second formula will be used in the programs, as the most resistant to overflows). After comparison, it turns out that the desired element is smaller than the average, and therefore the subsequent search is carried out on the left side of the sequence. The algorithm continues to execute in this way, until it is on step 4 of the desired element.

It is worth noting that it will take much less time here than if we used linear search, but unlike linear search, binary works only with arrays whose elements are ordered, which undoubtedly gives it negative specificity.

The code of the program in C++:

The code of the program in Pascal:

 

The program could check the array for the presence of elements in it, but since it is filled, regardless of the user, with a strictly defined number of constant values, this is not necessary.

 

In the case where the first mid value coincides with the key, then the algorithm is considered to have completed in its best O(1) time. In the average and worst case, the algorithm's running time is O(logn), which is significantly faster than that of linear search, which requires linear time.