Module: Busca binária por uma função monotônica


Problem

1/5

Busca binária por uma função monotônica

Theory Click to read/hide

A pesquisa binária pode ser usada não apenas para encontrar elementos em uma matriz, mas também para encontrar as raízes de equações e os valores de funções monotônicas (crescentes ou decrescentes).

Seja dada uma função monotônica f e algum valor C desta função. Encontre o valor do argumento x desta função, tal que \(f(x)=C\).
 
Exemplo de função monotônica crescente:


Escolhemos tais limites onde o valor da função é exatamente maior e exatamente menor que o valor dado. Vamos escolher o valor no meio deste segmento. Se for menor que o dado, deslocamos a borda esquerda para o meio do segmento. Caso contrário, deslocaremos a borda direita. Em seguida, repetimos o processo de estreitamento dos limites. Mas há um problema é que quando parar de procurar. Leia mais aqui.
 
Por exemplo, considere o problema de encontrar a raiz quadrada do número x. A raiz quadrada de x (indicada por \(\sqrt x\)) é um número y tal que < span class="math-tex">\(y^2 = x\).
Vamos formular o problema da seguinte forma: para um determinado número real x (\(x >= 1\)) encontre o raiz quadrada com precisão não inferior a 5 caracteres após o ponto.
 


Selecionando a borda do segmento para pesquisa

Como não podemos verificar toda a infinidade de números, precisamos definir os limites da busca pela raiz. Primeiro, vamos encontrar a borda esquerda, selecione um ponto negativo arbitrário (por exemplo: -1). Vamos dobrá-lo até que o valor nele seja maior que o valor fornecido. Para encontrar a borda certa, escolhemos um ponto positivo arbitrário (por exemplo: 1). Iremos dobrá-lo até que o valor da função neste ponto seja menor que o especificado.


Ou, se soubermos exatamente os limites da busca, podemos tomar 1 como o limite esquerdo e o próprio número x.
Depois disso, dividimos o segmento atual ao meio, quadramos o meio e, se for maior que x, substituímos a face superior, caso contrário  baixo.
 
Implementação final:

onde,
eps - a precisão com que a solução deve ser buscada,
x - número dado cuja raiz quadrada estamos procurando,
m - o número no qual o resultado será armazenado após a execução do algoritmo.
 

Problem

Dado um número natural x. Calcule a raiz cúbica de um número.
 
Entrada
Número x – natural, não excedendo \(10^6\).
 
Saída
O programa deve exibir um único número: a resposta do problema com uma precisão de pelo menos 6 casas decimais.

 

Exemplos
# Entrada Saída
1 2 1.259921

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>
using namespace std;

double Search_Binary(int x)
{           
	
}

int main()
{
	
	int x;
	cin >> x;
	
	double res = Search_Binary(x);
	printf("%.8lf", res);


}

     

Program check result

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