Module: Búsqueda binaria


Problem

1/5

Búsqueda binaria en matriz ordenada: inicio (C++)

Theory Click to read/hide

La búsqueda binaria es una — su estimación de complejidad es O(log2(n)), mientras que la búsqueda secuencial convencional tiene O(n). Esto significa que, por ejemplo, para una matriz de 1024 elementos, una búsqueda lineal, en el peor de los casos, cuando el elemento deseado no está en la matriz, procesará los 1024 elementos. La búsqueda binaria es suficiente para procesar elementos \(log_2(1024) = 10\). Este resultado se logra debido al hecho de que después del primer paso del bucle, el área de búsqueda se reduce a 512 elementos, después del segundo – hasta 256 etc.

Las desventajas de este algoritmo son el requisito de ordenar los datos, así como la capacidad de acceder a cualquier elemento de datos en un tiempo constante (independientemente de la cantidad de datos). Por lo tanto, el algoritmo no puede funcionar en matrices no ordenadas ni en ninguna estructura de datos basada en listas vinculadas.


Implementación
adiós (derecha – izquierda > 1)  // Siempre que el borde derecho esté a la derecha de la izquierda
nc
  medio = (izquierda + derecha) /< /span> 2; // Medio del área de búsqueda
  si (A[medio] >= b) entonces
    derecha = medio; // Mover el borde derecho
  de lo contrario
    izquierda = medio; // De lo contrario, mueva el borde izquierdo
cc
si (A[derecha] == X) entonces
  salida derecha;
de lo contrario
  salida -1;

donde:
A - matriz fuente,
N - tamaño de matriz,
X - el número deseado.
 

Problem

Implementar un algoritmo de búsqueda binaria.
 
Ingresar datos
La primera línea de la entrada contiene números naturales N y K (\(0<N <= 100000,\ 0< K< ;=10^9\) ). La segunda línea contiene los elementos N de la matriz, ordenados en orden ascendente. Los elementos de la matriz son números enteros, cada uno de los cuales no excede 109.
 
Salida
Se requiere que  K genere su número en la matriz en una línea separada, si este número aparece en la matriz, y "NO" de lo contrario.
 
Ejemplos

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++
# Entrada Salida
1
105
1 2 3 4 5 6 7 8 9 10
 5
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!