# 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:**

- the search zone (in the first step it is the entire array) is divided into two equal parts, by determining its middle
**(mid)**element; - 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.

- 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**.

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | #include "stdafx.h" #include <iostream> using namespace std; const int N=10; //binary search int BinarySearch(int A[], int key) { int left=0, right=N, mid; while (left<=right) { mid=left+(right-left)/2; if (key<A[mid]) right=mid-1; else if (key>A[mid]) left=mid+1; else return mid; } return -1; } // main function void main() { setlocale(LC_ALL,"Rus"); int i, key; int A[N]; cout<<"Searched element> "; cin>>key; // key input cout<<"Source array: "; for (i=0; i<N; i++) //filling and displaying the array { A[i]=N*i; cout<<A[i]<<" "; } if (BinarySearch(A, key)==-1) cout<<"\nElement not found"; else cout<<"\nElement number: "<<BinarySearch(A, key)+1; system("pause>>void"); } |

### The code of the program in Pascal:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | program BinSearch; usescrt; constN=10; type Arr=array[1..N] of integer; var mid, left, right, key, i: integer; A: Arr; {binary search} function BinarySearch(A: Arr; key: integer): integer; begin left:=1; right:=N; while left<=right do begin mid:=left+(right-left) div 2; if (key<A[mid]) then right:=mid-1 else if (key>A[mid]) then left:=mid+1 else begin BinarySearch:=mid; exit; end; end; BinarySearch:=-1; end; {main program block} begin write('Search item > '); read(key); {key input} write('Source array: '); for i:=1 to N do {fill and output array} begin A[i]:=N*i; write(A[i], ' '); end; writeln; if (BinarySearch(A, key)=-1) then write('Element not found') else write('Element number: ', BinarySearch(A, key)); end. |

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(log*n*), which is significantly faster than that of linear search, which requires linear time.