Module: Binary Search


Problem

1/5

Binary search in ordered array: start (C++)

Theory Click to read/hide

Binary search is an efficient — its complexity estimate is O(log2(n)), while conventional sequential search has O(n). This means that, 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. Binary search is enough to process \(log_2(1024) = 10\) elements. 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 this 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. Thus, the algorithm cannot work on unordered arrays and any data structures based on linked lists.


Implementation
bye (right – left > 1)  // As long as the right border is to the right of the left
nc
  middle = (left + right) /< /span> 2; // Middle of search area
  if (A[middle] >= b) then
    right = middle; // Move the right border
  otherwise
    left = middle; // Otherwise move the left border
cc
if (A[right] == X) then
  right output;
otherwise
  output -1;

where:
A - source array,
N - array size,
X - the desired number.
 

Problem

Implement a binary search algorithm.
 
Input data 
The first line of the input contains natural numbers N and K (\(0<N <= 100000,\ 0<K< ;=10^9\) ). The second line contains the N elements of the array, sorted in ascending order. The elements of the array are integers, each of which does not exceed 109.
 
Output
It is required for  K to output its number in the array on a separate line, if this number occurs in the array, and "NO" otherwise.
 
Examples
# Input Output
1
105
1 2 3 4 5 6 7 8 9 10 
 5

time 1000 ms
memory 32 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>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

int Search_Binary (vector<int> arr, int key)
{
	int  midd = 0, left =-1, right = arr.size();

             
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n, w, h, l, r, k, index;

	cin >> n >> k;

	vector<int> A(n);

	for (int i = 0; i < n; i++) {
		cin >> A[i];
	}

       index = Search_Binary (A, k);
 
	if (index >= 0) 
		cout << index+1;
	else
		cout << "NO";
}

     

Program check result

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