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:

бинарный поиск с++, binary search c ++, algorithm

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.

бинарный поиск с++, binary search c ++, algorithm

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.

бинарный поиск с++, binary search c ++, algorithm

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

бинарный поиск с++, binary search c ++, algorithm

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

Example:

Result:

бинарный поиск с++, binary search c ++, algorithm

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.

See also, how to implement binary search algorithm in C.

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

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

  2. 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?

Leave a Reply

Your email address will not be published. Required fields are marked *