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: