The basics of programming in c++ for beginners

# Binary (binary) search for c++

We have already dealt with the algorithm linear search. In the same article mentioned, that is not the only algorithm, which makes it possible to find the target value of the array. Existother search algorithms. Binary (binary) search is more efficient (checked asymptotic analysis of algorithms) the decision in the case, if the array is sorted in advance.

Supposing, the array of 12 elements sorted ascending:

The user sets the desired value (search key). Let's 4. On the first iteration array It is divided into two parts (We are looking for the middle element – midd): (0 + 11) / 2 = 5 (0.5 discarded). At first, checks the value of the middle element of the array. If it coincides with a key – the algorithm terminates and the program displays the message, that value is found. In our case, the key does not match the value of the middle item.

If the key is less than the average member, the algorithm will not be searched in one half of the array, which contains a value greater than the key (i.e.. from the middle to the end of the array element). The right edge of the search moves (midd – 1). Then again on the array division 2.

The key again is not equal to the middle element. It's more him. Now the left border of the search moves (midd + 1).

The third iteration of the middle element – a cell index 3: (3 + 4) / 2 = 3. It is the key. The algorithm terminates.

Example:

Result:

The binary search algorithm is effective - his assessment of the complexity of O(log2(n)), while an ordinary incremental search O(n). It means, that for example, for an array of 1024 elements of linear search in the worst case (when the desired item is not in the array) process all 1024 elements, but a binary search is enough to handle the log2(1024) = 10 elements. This result is achieved due to the fact, that after the first step, the search area is narrowed to loop 512 elements, After the second – to 256 etc.

The disadvantages of such an algorithm is the requirement of ordering data, as well as the ability to access any data element for the continued (independent of the number of data) time. Thus, the algorithm can not work on any disordered arrays and data structures, built on the basis of linked lists.

|

## 5 thoughts on “Binary (binary) search for c++”

1. Anna says:

Thank you. Very detailed and very clear beginner….

2. Victor says:

In the example, the error code, if you enter, for example, number 13, the latest iteration is already abroad array(midd = 12). The program does not fall and gives the correct result, because abroad there is an array of memory available to the process.

1. Nikita says:

int midd = 0;
while (1)
{
if(midd <=n)
{
midd = (left + right) / 2;
if (key arr[midd]) // If desired more value in the cell
{
left = midd + 1; // Search displace left border
}else // otherwise (значения равны)
{
cout<<"key[ "<<midd<<" ] = "<<key<<endl;
return midd; // function returns the index of the cell
}
}
} return -1;
}

Fixed, like, if not difficult to verify

1. Yang says:

if(midd <=n)
n — what's this?

3. Yura says:

For example an array of 20 numbers
Why did I enter in the search for the n-Noe number
I indicates the index before him?