Module: Pesquisa Binária


Problem

1/5

Pesquisa binária em array ordenado: start (C++)

Theory Click to read/hide

A pesquisa binária é uma ferramenta — sua estimativa de complexidade é O(log2(n)), enquanto a busca sequencial convencional tem O(n). Isso significa que, por exemplo, para um array de 1.024 elementos, uma busca linear, no pior caso, quando o elemento desejado não estiver no array, processará todos os 1.024 elementos. A pesquisa binária é suficiente para processar os elementos \(log_2(1024) = 10\). Este resultado é obtido devido ao fato de que após a primeira etapa do loop, a área de busca se reduz a 512 elementos, após a segunda – até 256 etc.

As desvantagens desse algoritmo são a exigência de ordenação de dados, bem como a capacidade de acessar qualquer elemento de dados em um tempo constante (independente da quantidade de dados). Assim, o algoritmo não pode funcionar em arrays não ordenados e quaisquer estruturas de dados baseadas em listas encadeadas.


Implementação
tchau (direita – esquerda > 1)  // Desde que a borda direita esteja à direita da esquerda
nc
  meio = (esquerda + direita) /< /span> 2; // Meio da área de pesquisa
  se (A[meio] >= b) então
    direito = meio; // Mova a borda direita
  caso contrário
    esquerda = meio; // Caso contrário, mova a borda esquerda
cc
se (A[direita] == X) então
  saída direita;
caso contrário
  saída -1;

onde:
A - matriz de origem,
N - tamanho do array,
X - o número desejado.
 

Problem

Implemente um algoritmo de busca binária.
 
Dados de entrada 
A primeira linha da entrada contém números naturais N e K (\(0<N <= 100000,\ 0< K< ;=10^9\) ). A segunda linha contém os elementos N da matriz, classificados em ordem crescente. Os elementos da matriz são inteiros, cada um dos quais não excede 109.
 
Saída
É necessário que  K exiba seu número na matriz em uma linha separada, se esse número ocorrer na matriz e "NO" caso contrário.
 
Exemplos
# Entrada Saída
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!