Module: Linear and binary search for elements in an array


Problem

6/7

Binary Search

Theory Click to read/hide

Binary Search
Binary (or binary) search is an efficient search algorithm and is faster than linear search. For example, for an array of 1024 elements, a linear search in the worst case (when the desired element is not in the array) will process all 1024 elements, but it is enough to process 10 elements with a binary search. This result is achieved due to the fact that after the first step of the loop, the search area narrows down to 512 elements, after the second – up to 256 etc.
 
The disadvantages of such an algorithm are the requirement for data ordering, as well as the ability to access any data element in a constant (independent of the amount of data) time. Therefore, the algorithm cannot work on unordered arrays.
 
Algorithm
  1. Select middle element A[c] and compare with X.
  2. If X = A[c] then found (stop).
  3. If X < A[c], search further in the first half.
  4. If X > A[c], look further into the second half.
     
Implementation
L = 0; R=N; // initial segment while ( L < R - 1) { c = (L + R) / 2; // found the middle if ( X < A[c] ) // segment compression R=c; else L = c; } if ( A[L] == X) cout << "A" << L<< "]=" << x; else cout << "Not found";

where:
A - source array,
N - array size,
X - searched number,

Other implementations are possible.
For example, using an early exit from the loop L = 0; R = N - 1; while (R >= L) { c = (L + R) / 2; if ( X == A[c] ) { nX = c; break; } if (X < A[c]) R = mid - 1; if (X > A[c]) L = mid + 1; } if ( nX < 0) cout << "Not found"; else cout << "A" << nX<< "]=" << X;

Problem

In the given array, sorted in ascending order, you need to find the value of the element equal to the value X using binary search. X is entered from the keyboard. Modify the program so that it solves the problem The numbering of elements starts from zero. If there is no such element, the program should output Not found.

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
Write the program below 
#include<iostream> 
using namespace std; 
main() 
{	
  const int Nmax=1000; 	
  int A[Nmax], i, L, R, X, N, c;	 
  cin >> N; 
  for (i=0; i<N; i++) 
    cin >> A[i]; 
  cin >> X; 
  L = 0; R = N;       
  while ( L < R-1 ) 
       cout << "A["<< L << "]=" << X; 
  else cout << "Not found"; 
}

     

Program check result

To check the solution of the problem, you need to register or log in!